问题描述
假设我们有n件物品，分别编号为1, 2…n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。
现在，假设我们有一个背包，它能够承载的重量是W。假定我们这里选取的物品每个都是独立的，不能选取部分，也就是说我们要么选取某个物品，要么不能选取，不能只选取一个物品的一部分。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？
问题分析
- 变量
- 当前背包剩余重量LW
- 编号index的物品价值vi,重量wi
- 从最大价值的物品开始放入
- 如果当前物品index不能入背包，也就是
wi>LW,那么物品index的背包价值等于index-1的背包价值 - 如果当前物品index能放入背包，并且index的背包价值大于不放入index的背包价值，即
vi+v(i-1)>skipValue，那么index的背包价值就是CurValue+v(i-1) - 如果当前物品index能放入背包，但是index之前的物品组合价值
skipValue>vi+v(i-1)，那么物品index不应该放入背包,index的背包价值skipValue
解法1-递归
int bagValues(vector<int> values, vector<int> weights,int LW, int index) {
//边界
if (LW <= 0 || index < 0) {
return 0;
}
//`wi>LW`时，价值等于index-1的背包价值
if (weights[index] > LW) {
return bagValues(values, weights,LW,index - 1);
} else {
//放入index之后的价值=当前价值+(index-1在剩余空间的的背包价值)
int vi = values[index] + bagValues(values, weights,LW - weights[index],index-1);
//不放入index之后的价值
int skipValue = bagValues(values, weights, LW, index-1);
//最大值
return max(vi, skipValue);
}
}
解法2-递归优化
解法1存在着重复计算的地方，所以可以用数组保存计算结果
int bagValues1(vector<int> values, vector<int> weights,int LW, int index,vector<vector<int>> L) {
//边界
if (LW <= 0 || index < 0) {
return 0;
}
//没有有缓存
if (L[index][LW] < 0) {
//`wi>LW`时，价值等于index-1的背包价值
if (weights[index] > LW) {
L[index][LW] = bagValues1(values, weights,LW,index - 1,L);
} else {
//放入index之后的价值=当前价值+(`index-1[剩余空间]`的背包价值)
int vi = values[index] + bagValues1(values, weights,LW - weights[index],index-1,L);
//不放入index之后的前一价值
int skipValue = bagValues1(values, weights, LW, index-1,L);
//最大值
L[index][LW] = max(vi, skipValue);
}
}
return L[index][LW];
}
解法3-递推
int bagValues2(vector<int> values, vector<int> weights,int LW, int index) {
//边界
if (LW <= 0 || index < 0) {
return 0;
}
vector<vector<int>> L= vector<vector<int>>(index+1,vector<int>(LW+1,0));
/*
编号 0 1 2 3 4 5 6 //重量
0 0 0 0 0 0 0 0
1 0 16 16 16 16 16 16
2 0 16 16 28 28 28 28
3 0 16 16 28 28 28 29
*/
for (int i = 1; i <= index; i++ ) {
//当前重量
int curWeight = weights[i-1];
//当前价值
int curValue = values[i-1];
for (int j = 1; j <= LW; j++) {
//`wi>LW`时，价值等于前一行i-1的背包价值
if (curWeight > j) {
L[i][j] = L[i-1][j];
} else {
//放入i之后的价值=当前价值+(前一行`i-1[剩余空间]`的最大价值)
int vi = curValue + L[i-1][j-curWeight];
//不放入i之后 前一行`i-1[现在最大空间]`的最大价值
int skipValue = L[i-1][j];
//最大值
L[i][j] = max(vi, skipValue);
}
}
}
return L[index][LW];
}
解法4-递推空间优化
int bagValues3(vector<int> values, vector<int> weights,int LW, int index) {
//边界
if (LW <= 0 || index < 0) {
return 0;
}
vector<int> L= vector<int>(LW+1,0);
vector<int> M = vector<int>(LW+1,0);
/*
编号 0 1 2 3 4 5 6 //重量
0 0 0 0 0 0 0 0
M 1 0 16 16 16 16 16 16
L 2 0 16 16 28 28 28 28
3 0 16 16 28 28 28 29
*/
for (int i = 1; i <= index; i++ ) {
//当前重量
int curWeight = weights[i-1];
//当前价值
int curValue = values[i-1];
for (int j = 1; j <= LW; j++) {
if (curWeight > j) {
//前一行M`[当前最大空间]`价值
L[j] = M[j];
} else {
//放入index之后的价值=当前价值+(前一行`M[剩余空间]`的背包价值)
int vi = curValue + M[j-curWeight];
//不放入index，前一行M`[当前最大空间]`价值
int skipValue = M[j];
//最大值
L[j] = max(vi, skipValue);
}
}
M = L;
}
return L[LW];
}
测试代码
//
vector<int> values = {16, 12, 1};
vector<int> weights = {1, 2, 3};
int index = (int)values.size();
int LW = 6;
// int CurValue = 0;
int m = bagValues(values, weights,LW,index-1);
cout<<m<<endl;
//m*n
vector<vector<int>> L1= vector<vector<int>>(values.size()+1,vector<int>(LW+1,-1));
int m1 = bagValues1(values, weights,LW,index-1, L1);
cout<<m1<<endl;
//m*n
int m2 = bagValues2(values, weights,LW,index);
cout<<m2<<endl;
//m*n
int m3 = bagValues3(values, weights,LW,index);
cout<<m3<<endl;
//打印结果
29
29
29
29
