背包问题

0-1背包

A thief robbing a store finds n items.The ith item is worth $w_i$ dollars and weighs $w_i$ pounds,where $v_i$ and $w_i$ pounds,where $v_i$ and $w_i$ are integers.The thief wants to take as valuable a load as possible,but he can carry at most W pounds in his knapsack,for some integer W.which items should he take?

令dp[i][j]为前i个物品，载重为j的最大价值，那么最大价值取决于第i个物品拿不拿

  • 不拿：dp[i-1][j]
  • 拿：dp[i-1][j-w[i]]+v[i]

然后选择较大者即可

但是你发现第一维是可以优化掉的：前i个物品只和前i-1个物品有关

但是注意数组滚动的方向是j由大到小，以防前面的被覆盖了，因为dp[j]依赖的是前i-1个物品的结论，覆盖了的话就成了前i个物品了

（但是二维形式不需要刻意逆向，因为不会遭遇覆盖的问题，无脑正向）

1
2
3
4
5
6
7
8
9
10
int backPackII(int m, vector<int> &A, vector<int> &V) {
    auto items=A.size();
    vector<int> dp(m+1);
    for(int i=0;i<items;++i){
        for(int j=m;j>=A[i];--j){
            dp[j]=std::max(dp[j],dp[j-A[i]]+V[i]);
        }
    }
    return dp[m];
}

完全背包

完全背包是在0-1背包的基础上，令一件物品可以有无限个，但其问题实际上还是0-1背包，但是必须多考虑一个表示个数的变量：

这样使得子问题增多了，我们消掉k从而优化子问题空间：

我们有：

于是，我们最终得到消掉k的状态转移方程

用滚动数组优化第一维：

完了，你发现这个和0-1背包的一维形式完全一样，但是注意它们的二维形式不同，而这决定了滚动方向：完全背包的滚动方向是由小到大

因为它不像0-1背包完全建立于前i-1个物品的基础上，它也建立于前i个物品的基础上，因此从小开始滚动

分数背包

背包方案数

给出 n 个物品, 以及一个数组, nums[i]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品可以使用无数次

由”每个物品有无限个”可以看出这是完全背包问题的变种

定义dp[i][j]表示前i个物品容纳j大小的方案数，将第i个物品不取走或取k次，方案数与减去该物品大小的k倍是相等的，那么dp[i][j]等于dp[i-1][j-knums[i]]的总和,因此状态转移方程为：

滚动数组压缩空间：dp[j]表示容纳j大小的方案数，该方案数只和之前的方案数相关，即dp[j-nums[i]]

因为每个物品有无限个，因此正向滚动

纯公式推导：

令w=j-nums[i]，我们有

进而：

消去第一维：

1
2
3
4
5
6
7
8
9
10
int backPackIV(vector<int> &nums, int target) {
    auto items=nums.size();
    vector<int> dp(target+1);
    dp[0]=1;
    for(int i=1;i<=items;++i){
        for(int j=nums[i-1];j <= target;++j)
            dp[j]+=dp[j-nums[i-1]];
    }
    return dp[target];
}