01背包问题

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

此处最简单的方式就是使用回溯法去暴力求解：每一个物品有且仅有两种状态，放入背包或不放入背包，时间复杂度。

使用动态规划进行求解，削减时间复杂度：此处的重点依旧在于问题的划分上。

动态规划的过程

首先使用经典的动态规划方式进行问题的划分：

动态规划数组的定义：dp[i] 表示最多能背重量为 i 的背包能够装的物品的价值总和。
动态规划数组的推导：当 weight[j]<i 时， dp[i]=max(dp[i-weight[j]]+value[j]) 其中 j=0..n
动态规划数组的初始化：此处在进行数组的初始化时，就会出现问题，并且这样的处理还存在一个问题，无法处理小数的情况（通常是整数）

使用二维的动态规划数组进行处理：

动态规划数组的定义： dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
动态规划数组的推导：对于 dp[i][j] 相较于上一行 dp[i-1][j] 背包的容量是相同的，但是可选的物品多了一个 i ，那么要么尝试选择物品 i （若是 weight[i]<=j ）就有 dp[i][j]=value[i]+dp[i-1][j-weight[i]] ，要么不选取物品 i 那么依旧是从前 i-1 个物品中进行选取，那么 dp[i][j]=dp[i-1][j] ，在上述两种情况中取最大值即可。那么就有 dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
动态规划数组的初始化：对于第一列 dp[i][0] 容量为0，那么全部初始化为0，对于第一行 dp[0][j] ，在 weight[0]>j 时全部初始化为0，当 weight[0]<=j 时，全部初始化为 value[0]
动态规划数组的遍历方式：在计算 dp[i][j] 时，将会使用到前行的信息，所以采取从左向右逐行遍历的方式。（实际上在计算 dp[i][j] 所使用到的前面的 dp[a][b] 的信息，此处的 a<i&&b<j 所以，采取逐列遍历的方式也是可以的。）
举例验证：对于 vector<int> weight={1,3,4}; vector<int> value={15,20,30}; 情形，按照上述方式计算得到的值为35，验证正确。

代码实现：

#include<iostream>
#include<vector>
#include<algorithm>
using std::vector;
using std::max;
int backpack01(vector<int>& weight,vector<int>& value,int w){
    int n=weight.size();
    vector<vector<int>> dp;
    dp.resize(n,vector<int>(w+1,0));
    for(int i=weight[0];i<=w;i++){ // 直接从第一个物品的容量开始
        dp[0][i]=value[0];
    }
    for(int i=1;i<n;i++){ // 总计n行
        for(int j=1;j<=w;j++){
            if(j>=weight[i]){ // 能够放下
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    return dp[n-1][w];
}
int main(){
    vector<int> weight={1,3,4};
    vector<int> value={15,20,30};
    std::cout<<backpack01(weight,value,4);
}

使用滚动数组优化空间复杂度

此处在进行 dp[i][j] 数组的计算时，实际上只需要使用到前一行中 dp[i-1][j] 和 dp[i-1][j-weight[i]] 的信息，因此可以使用一个一维数组来实现。

使用滚动数组的实现方式：想要计算第 i+1 行的信息，将第 i 行作为第 i+1 行的初始值，并且此处在计算 dp[i][j] 时还需要使用到 dp[i-1][j-weight[i]] 的信息，在使用滚动数组的前提下也就是需要使用 dp[i][j-weight[i]] 的信息，那么在行内的遍历方式就需要从右向左进行。从实际问题的角度出发去理解：若是采取从左向右的便利方式，那么就会出现物品被重复放入的问题，在第 i 次迭代中， dp[k] 将物品 i 放入一次，计算得到新的 dp[k] ，在 dp[k+1] 时可能再次放入 i 并且使用 dp[k] 去更新 dp[k+1] 这就出现了重复放置的问题。

动态规划数组的定义：初始 dp[j] 表示，在物品 0 中选取，容量为 j 的背包能够得到的最大价值，在迭代 i 次后， dp[j] 表示在物品 0-i 中选取，容量为 j 的背包能够得到的最大价值。 dp.size()=w+1
动态规划数组的递推：对于 dp[j] 在第 i 次迭代时，dp[j]=max(dp[j],dp[j-weight[i]]+value[i]) if j>=weiht[i] else dp[j]
动态规划数组的初始化：依旧是 dp[i]=value[0] if i>=weight[0] else 0
动态规划数组的遍历顺序：首先是对从前向后对物品进行遍历 i=1,...,n-1 ，再从右向左对背包进行遍历 j=w,...,1 (此处背包为0的情况直接省略，无须遍历)
举例验证：对于 vector<int> weight={1,3,4}; vector<int> value={15,20,30}; 情形，按照上述方式计算得到的值为35，验证正确。

代码实现：

在上述的遍历过程可以进行进一步的改写，对于 j 的取值范围，当 j<weight[i] 时在继续遍历实际上就没有意义了，此时 dp[j]=dp[j] 即可。因此 j 的范围是 w,...,weight[i]

#include<iostream>
#include<vector>
#include<algorithm>
using std::vector;
using std::max;
int backpack01(vector<int>& weight,vector<int>& value,int w){
    int n=weight.size();
    vector<int> dp(w+1,0);
    for(int i=weight[0];i<=w;i++)
        dp[i]=value[0];
    for(int i=1;i<n;i++){
        for(int j=w;j>=weight[i];j--){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    return dp[w];
}
int main(){
    vector<int> weight={1,3,4};
    vector<int> value={15,20,30};
    std::cout<<backpack01(weight,value,4);
}