背包问题
01背包
状态：f(i,j) 表示只能装前i个物品的情况下，容量为j的背包所能达到的最大总价值
状态转移方程： f(i,j)=max(f(i-1,j),f(i-1,j-w[i])+v[i])
核心代码（滚动数组） 由于我们使用一维数组存储，则在求两个子问题时没有直接取出那么方便了，因为第i次循环可能覆盖第i-1次循环的结果
“相反，如果在执行第 i 次循环时，背包容量按照0..V的顺序遍历一遍，来检测第 i 件物品是否能放。此时在执行第i次循环 且 背包容量为v时，此时的f[v]存储的是 f[i - 1][v] ，但是，此时f[v-weight[i]]存储的是f[i][v-weight[i]]。
因为，v > v - weight[i]，第i次循环中，执行背包容量为v时，容量为v - weight[i]的背包已经计算过，即f[v - weight[i]]中存储的是f[i][v - weight[i]]。即，对于01背包，按照增序枚举背包容量是不对的。”
for (int i = ; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}但是，增序枚举会达到什么效果：它会重复的装入某个物体，而且尽可能的多使价值增大
01背包方案数问题
洛谷P1164 小A点菜 https://www.luogu.com.cn/problem/P1164
“
开个玩笑，这是一道简单的动规题，定义f[i][j]为用前i道菜用光j元钱的办法总数，其状态转移方程如下：
（1）if(j==第i道菜的价格)f[i][j]=f[i-1][j]+1;
（2）if(j>第i道菜的价格) f[i][j]=f[i-1][j]+f[i-1][j-第i道菜的价格];
（3）if(j<第i道菜的价格) f[i][j]=f[i-1][j];
”
code1
const int maxn = ;
int n, m, w[maxn], f[maxn][]; int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
scanf("%d", &w[i]);
}
for (int i = ; i <= n; i++) {
f[i][] = ;
} for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
f[i][j] += f[i - ][j];
if (j >= w[i]) f[i][j] += f[i - ][j - w[i]];
}
} printf("%d", f[n][m]);
return ;
}
code2
const int maxn = ;
int n, m, w[maxn], f[]; int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
scanf("%d", &w[i]);
}
f[] = ; for (int i = ; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] += f[j - w[i]];
}
}
printf("%d", f[m]);
return ;
}
:
完全背包问题
状态转移方程： f(i,j)=max(f(i-1,j),f(i,j-w[i])+v[i]) 理由是当我们这样转换时，f(i,j-w[i])已经由f(i,j-2*w[i]) 更新过，那么f(i,j-w[i])就是充分考虑了第i件物品后的最优结果换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。
for (int i = ; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}多重背包问题
考虑二进制优化
时间复杂度O(NWlog∑mi)
luogu P1776 宝物筛选https://www.luogu.com.cn/problem/P1776
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std; const int maxn = ;
const int maxm = ; int n, m, ans, cnt = ;
int f[maxn];
int w[maxn], v[maxn]; int main() {
int a, b, c;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
scanf("%d%d%d", &a, &b, &c);
for (int j = ; j <= c; j << ) {
v[++cnt] = j * a;
w[cnt] = j * b;
c -= j;
}
if (c) v[++cnt] = a * c, w[cnt] = b * c; //二进制优化 拆分
}
for (int i = ; i <= cnt; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
printf("%d\n", f[m]);
return ;
}
HDU 2844 Coins(多重背包）
注意：本题只关注“可行性”
因此不妨变换思路求解
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std; int vis[];
int a[];
int c[];
int f[]; int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
if (n == m && n == ) break;
memset(f, , sizeof f);
f[] = ;
for (int i = ; i<=n; i++) scanf("%d", &a[i]);
for (int i = ; i <=n; i++) scanf("%d", &c[i]);
for (int i = ; i <=n; i++) {
memset(vis, , sizeof vis);
for (int v = a[i]; v <= m; v++) {
if ((!f[v]) && (vis[v-a[i]] < c[i]) && f[v - a[i]]) {
vis[v] = vis[v - a[i]] + ;
f[v] = ;
}
}
}
int cnt = ;
for (int i = ; i <= m; i++) if (f[i]) cnt++;
printf("%d\n", cnt);
}
return ;
}
分组背包 （三重循环）
状态转移方程 f(k,v)=max(f(k-1,v),f(k-1,v-ci)+wi|i属于group k)
时间复杂度O（NV)
HDU1712 ACboy needs your help
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std; int mp[][];
int f[];
int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
memset(f, , sizeof f);
if (n == && n == m) break;
for (int i = ; i <=n; i++) {
for (int j = ; j <=m; j++) {
scanf("%d", &mp[i][j]);
}
}
for (int i = ; i <=n; i++) {
for (int v = m; v>=; v--) {
for (int j =; j <=m; j++) {
if(v>=j) f[v] = max(f[v], f[v - j] + mp[i][j]);
}
}
}
printf("%d\n", f[m]);
}
return ;
}
初始化问题：
“初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。
如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。
如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。”