DP
多重背包问题 I
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
版本1 二维
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1;i <= n; i++)
for(int j = 0;j <= m; j++)
for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout << f[n][m] << endl;
return 0;
}
版本2 二进制优化为一维
我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。
状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i])
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25000, M = 2010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
cin >> n >> m;
int cnt = 1;
for(int i = 1; i <= n; i++){
int a,b,s;
cin >> a >> b >> s;
int k = 1;
while(k <= s){
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0){
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for(int i = 1;i <= n; i++)
for(int j = m;j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
分组背包问题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];
int main(){
cin >> n >> m;
int cnt = 1;
for(int i = 0; i < n; i++){
cin >> s[i];
for(int j = 0; j < s[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for(int i = 0;i < n; i++)
for(int j = m;j >= 0; j--)
for(int k = 0; k < s[i]; k++){
if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
cout << f[m] << endl;
return 0;
}
