01背包
f[i][j] 前i个物品选择一些恰填满容量为j的背包，需要的最小物品数
边界：
1
2
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
状态转移方程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1; i<=n; i++) {
for(int j=0; j<=m; j++) {
if(j >= v[i])
f[i][j] = min(f[i-1][j], f[i-1][j-v[i]] + 1);
else
f[i][j] = f[i-1][j];
}
}
// 降维：
for(int i=1; i<=n; i++) {
for(int j=v[i]; j<=m; j++) {
f[j] = min(f[j], f[j-v[i]] + 1);
}
}
完全背包
f[i][j] 前i个物品选择一些恰填满容量为j的背包，需要的最小物品数
边界：
1
2
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
状态转移方程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1; i<=n; i++) {
for(int j=0; j<=m; j++) {
if(j >= v[i])
f[i][j] = min(f[i-1][j], f[i][j-v[i]] + 1);
else
f[i][j] = f[i-1][j];
}
}
// 降维：
for(int i=1; i<=n; i++) {
for(int j=v[i]; j<=m; j++) {
f[j] = min(f[j], f[j-v[i]] + 1);
}
}
多重背包
f[i][j] 前i个物品选择一些恰填满容量为j的背包，需要的最小物品数
边界：
1
2
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
状态转移方程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i=1; i<=n; i++) {
for(int j=0; j<=m; j++) {
for(int k=0; k<=c[i]; k++) {
if(j >= k*v[i])
f[i][j] = min(f[i][j], f[i-1][j-k*v[i]] + k);
else
break;
}
}
}
// 降维：
for(int i=1; i<=n; i++) {
for(int j=m; j>=0; j--) {
for(int k=0; k<=c[i]; k++) {
if(j >= k*v[i])
f[j] = min(f[j], f[j-k*v[i]] + k);
else
break;
}
}
}
