动态规划-背包问题

问题描述

假设我们有n件物品，分别编号为1, 2…n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。

现在，假设我们有一个背包，它能够承载的重量是W。假定我们这里选取的物品每个都是独立的，不能选取部分，也就是说我们要么选取某个物品，要么不能选取，不能只选取一个物品的一部分。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？

问题分析

1. 变量
   • 当前背包剩余重量LW
   • 编号index的物品价值vi,重量wi
2. 从最大价值的物品开始放入
3. 如果当前物品index不能入背包，也就是wi>LW,那么物品index的背包价值等于index-1的背包价值
4. 如果当前物品index能放入背包，并且index的背包价值大于不放入index的背包价值，即vi+v(i-1)> skipValue，那么index的背包价值就是CurValue+v(i-1)
5. 如果当前物品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