問(wèn)題描述
假設(shè)我們有n件物品，分別編號(hào)為1, 2…n渊啰。其中編號(hào)為i的物品價(jià)值為vi探橱，它的重量為wi。為了簡(jiǎn)化問(wèn)題绘证，假定價(jià)值和重量都是整數(shù)值隧膏。
現(xiàn)在，假設(shè)我們有一個(gè)背包嚷那，它能夠承載的重量是W胞枕。假定我們這里選取的物品每個(gè)都是獨(dú)立的，不能選取部分魏宽，也就是說(shuō)我們要么選取某個(gè)物品腐泻，要么不能選取，不能只選取一個(gè)物品的一部分《友現(xiàn)在派桩，我們希望往包里裝這些物品，使得包里裝的物品價(jià)值最大化蚌斩，那么我們?cè)撊绾蝸?lái)選擇裝的東西呢铆惑？
問(wèn)題分析
- 變量
- 當(dāng)前背包剩余重量LW
- 編號(hào)index的物品價(jià)值vi,重量wi
- 從最大價(jià)值的物品開(kāi)始放入
- 如果當(dāng)前物品index不能入背包，也就是
wi>LW,那么物品index的背包價(jià)值等于index-1的背包價(jià)值 - 如果當(dāng)前物品index能放入背包送膳，并且index的背包價(jià)值大于不放入index的背包價(jià)值员魏，即
vi+v(i-1)>skipValue，那么index的背包價(jià)值就是CurValue+v(i-1) - 如果當(dāng)前物品index能放入背包叠聋，但是index之前的物品組合價(jià)值
skipValue>vi+v(i-1)撕阎，那么物品index不應(yīng)該放入背包,index的背包價(jià)值skipValue
解法1-遞歸
int bagValues(vector<int> values, vector<int> weights,int LW, int index) {
//邊界
if (LW <= 0 || index < 0) {
return 0;
}
//`wi>LW`時(shí)，價(jià)值等于index-1的背包價(jià)值
if (weights[index] > LW) {
return bagValues(values, weights,LW,index - 1);
} else {
//放入index之后的價(jià)值=當(dāng)前價(jià)值+(index-1在剩余空間的的背包價(jià)值)
int vi = values[index] + bagValues(values, weights,LW - weights[index],index-1);
//不放入index之后的價(jià)值
int skipValue = bagValues(values, weights, LW, index-1);
//最大值
return max(vi, skipValue);
}
}
解法2-遞歸優(yōu)化
解法1存在著重復(fù)計(jì)算的地方碌补，所以可以用數(shù)組保存計(jì)算結(jié)果
int bagValues1(vector<int> values, vector<int> weights,int LW, int index,vector<vector<int>> L) {
//邊界
if (LW <= 0 || index < 0) {
return 0;
}
//沒(méi)有有緩存
if (L[index][LW] < 0) {
//`wi>LW`時(shí)虏束，價(jià)值等于index-1的背包價(jià)值
if (weights[index] > LW) {
L[index][LW] = bagValues1(values, weights,LW,index - 1,L);
} else {
//放入index之后的價(jià)值=當(dāng)前價(jià)值+(`index-1[剩余空間]`的背包價(jià)值)
int vi = values[index] + bagValues1(values, weights,LW - weights[index],index-1,L);
//不放入index之后的前一價(jià)值
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));
/*
編號(hào) 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++ ) {
//當(dāng)前重量
int curWeight = weights[i-1];
//當(dāng)前價(jià)值
int curValue = values[i-1];
for (int j = 1; j <= LW; j++) {
//`wi>LW`時(shí)名斟，價(jià)值等于前一行i-1的背包價(jià)值
if (curWeight > j) {
L[i][j] = L[i-1][j];
} else {
//放入i之后的價(jià)值=當(dāng)前價(jià)值+(前一行`i-1[剩余空間]`的最大價(jià)值)
int vi = curValue + L[i-1][j-curWeight];
//不放入i之后 前一行`i-1[現(xiàn)在最大空間]`的最大價(jià)值
int skipValue = L[i-1][j];
//最大值
L[i][j] = max(vi, skipValue);
}
}
}
return L[index][LW];
}
解法4-遞推空間優(yōu)化
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);
/*
編號(hào) 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++ ) {
//當(dāng)前重量
int curWeight = weights[i-1];
//當(dāng)前價(jià)值
int curValue = values[i-1];
for (int j = 1; j <= LW; j++) {
if (curWeight > j) {
//前一行M`[當(dāng)前最大空間]`價(jià)值
L[j] = M[j];
} else {
//放入index之后的價(jià)值=當(dāng)前價(jià)值+(前一行`M[剩余空間]`的背包價(jià)值)
int vi = curValue + M[j-curWeight];
//不放入index，前一行M`[當(dāng)前最大空間]`價(jià)值
int skipValue = M[j];
//最大值
L[j] = max(vi, skipValue);
}
}
M = L;
}
return L[LW];
}
測(cè)試代碼
//
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;
//打印結(jié)果
29
29
29
29
