题目描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
样例
input:
3 5
2
1 2
2 4
1
3 4
1
4 5
output:
8
C++ 代码
显然状态转移方程为
f[i,j]=max(f[i-1][j],f[i-1,j-v[i,k]]+w[i,k])
其实这个状态转移方程只是粗略的,有很多问题。
依照这个方程粗略地写出代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];
int main()
{
int m, n;
cin >> m >> n; //m=N,n=V
for (int i = 1; i <= m; i++)
{
cin >> s[i];
for (int j = 1; j <= s[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= m; i++)
for (int j = 0; j <= n; j++)
for (int k = 1; k <= s[i] && j >= v[i][k]; k++)
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]);
cout << f[m][n] << endl;
return 0;
}
wa了个痛快!
那么错在哪里呢?
首先让我们写出正确的代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];
int main()
{
int m, n;
cin >> m >> n; //m=N,n=V
for (int i = 1; i <= m; i++)
{
cin >> s[i];
for (int j = 1; j <= s[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= m; i++)
for (int j = 0; j <= n; j++)
for (int k = 1; k <= s[i]; k++){
f[i][j] = max(f[i-1][j], f[i][j]);
if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
cout << f[m][n] << endl;
return 0;
}
首先是循环体的K的条件,
for(int k=0;k<=s[i]&&v[i][k]<=j;k++)
这么写有什么问题呢?
v[i] [k]关于k并不是递增的,所以当前的k不满足要求,并不意味着后面的k也不满足要求,不能结束循环,应该改成:
if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
还有一个小细节!那就是
f[i][j] = max(f[i-1][j], f[i][j]);
因为有可能这一层一个也放不下,但是你不这么写的话那么当前层就为0,而实际应该更新为上一层的值才对。
不得不说压缩成一维才是真的香!!!
我们看一维的
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N], s[N], v[N][N], w[N][N];
int main()
{
int m, n;
cin >> m >> n; //m=N,n=V
for (int i = 1; i <= m; i++)
{
cin >> s[i];
for (int j = 1; j <= s[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= m; i++)
for (int j = n; j >= 0; j--)
for (int k = 1; k <= s[i]; k++){
//f[i][j] = max(f[i-1][j], f[i][j]);
if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
cout << f[n] << endl;
return 0;
}
注意一下这里注释的地方,删掉了一维就是恒等式了,所以可以省略不写,但写二维的时候一定要写