OI-Knowledge：0-1背包

0-1背包

题目描述

有 $n$ 个物品，第 $i$ 个物体的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品至多选一个，求体积和不超过 $capacity$ 时的最大价值和。

解决思路

后续代码解决该例题：P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解法1：记忆化搜索

首先考虑最直观的想法，就是使用记忆化搜索， $dfs(i,c)$ 表示的是当剩余容量为c时，从前i个物品中得到的最大价值。

需要解决的子问题就是当剩余c的容量时，第i个物品选还是不选。当前状态可以由如下方程转移（含义是选还是不选第i个物品）：

dfs(i,c)=\max (dfs(i-1, c),dfs(i-1, c-w[i])+v[i])

实现代码如下：

class Solution {
public:
    int solve(vector<int>& times, vector<int>& vals, int T){
        int n = times.size();
        vector<vector<int>> dp(n+1, vector<int>(T+1,-1));
        function<int(int,int)> dfs = [&](int i, int c) {
            if (i < 0) return 0;
            if (dp[i][c] >= 0) return dp[i][c];

            dp[i][c] = dfs(i - 1, c);
            if (times[i] > c) return dp[i][c];
            dp[i][c] = max(dfs(i-1,c-times[i])+vals[i], dp[i][c]);
            return dp[i][c];
        };
        return dfs(n-1,T);
    }
};

解法2：递推

知道了记忆化搜索的解决方法，那么递推也非常好实现。

class Solution {
public:
    int solve(vector<int>& times, vector<int>& vals, int T){
        int n = times.size();
        vector<vector<int>> dp(n+1, vector<int>(T+1,0));
        for(int i=0;i<n;++i){
            for(int j=0;j<=T;++j){
                if (j < times[i]) dp[i+1][j] = dp[i][j];
                else dp[i+1][j] = max(dp[i][j],dp[i][j-times[i]]+vals[i]);
            }
        }
        return dp[n][T];
    }
};

解法3：滚动数组

当然还可以使用滚动数组对空间复杂度进一步优化：

注意：第二层循环是倒着循环的，确保每个物品最多被选1次

class Solution {
public:
    int solve(vector<int>& times, vector<int>& vals, int T){
        int n = times.size();
//        vector<vector<int>> dp(n+1, vector<int>(T+1,0));
        vector<int> dp(T+1, 0);
        for(int i=0;i<n;++i){
            for(int j=T;j>=0;--j){
                if (j >= times[i]) dp[j] = max(dp[j],dp[j-times[i]]+vals[i]);
            }
        }
        return dp[T];
    }
};

完全背包

题目描述

有 $n$ 个物品，第 $i$ 个物体的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品可以无限次重复选择，求体积和不超过 $capacity$ 时的最大价值和。

解决思路

后续代码解决该例题：P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解法1：记忆化搜索

相比之前的公式，有一点小变化,就是在选择当前物品的dp数组上i-1变为i

dfs(i,c)=\max (dfs(i-1, c),dfs(i, c-w[i])+v[i])

该变化表明，在选择了第i件物品后，你还可以继续选择第i件物品。

代码也仅有一点小变化，实现代码如下：

class Solution {  
public:  
    int solve(vector<int>& times, vector<int>& vals, int T){  
        int n = times.size();  
        vector<vector<int>> dp(n+1, vector<int>(T+1,-1));  
        function<int(int,int)> dfs = [&](int i, int c) {  
            if (i < 0) return 0;  
            if (dp[i][c] >= 0) return dp[i][c];  
  
            dp[i][c] = dfs(i - 1, c);  
            if (times[i] > c) return dp[i][c];  
            dp[i][c] = max(dfs(i,c-times[i])+vals[i], dp[i][c]);  
            return dp[i][c];  
        };        return dfs(n-1,T);  
    }};

解法2：递推

同理，一点小变化：

class Solution {
public:
    int solve(vector<int>& times, vector<int>& vals, int T){
        int n = times.size();
        vector<vector<int>> dp(n+1, vector<int>(T+1,0));
        for(int i=0;i<n;++i){
            for(int j=0;j<=T;++j){
                if (j < times[i]) dp[i+1][j] = dp[i][j];
                else dp[i+1][j] = max(dp[i][j],dp[i+1][j-times[i]]+vals[i]);
            }
        }
        return dp[n][T];
    }
};

解法3：滚动数组

同理也可以使用滚动数组对空间复杂度进一步优化：

注意：此时第二层循环是正着循环的，确保每个物品能够被多次选择

class Solution {
public:
    long long solve(vector<long long>& times, vector<long long>& vals, long long T){
        long long n = times.size();
//        vector<vector<long long>> dp(n+1, vector<long long>(T+1,0));
        vector<long long> dp(T+1, 0);
        for(long long i=0;i<n;++i){
            for(long long j=0;j<=T;++j){
                if (j >= times[i]) dp[j] = max(dp[j],dp[j-times[i]]+vals[i]);
            }
        }
        return dp[T];
    }
};

背包变体

上面我们展现了两种常见背包的模板问题以及他们的解决方法，下面我们讨论一下背包问题常见的三种变形，他们分别是：

至多装 $capacity$ ，求方案数/最大价值和
恰好装 $capacity$ ，求方案数/最大/最小价值和
至少装 $capacity$ ，求方案数/最小价值和

上面展示的两种背包的板题都是基于第一种变形。

变形2

01背包

题目传送门：494. 目标和 - 力扣（LeetCode）

使用数学公式转换一下，可以发现此题是一个恰好得到n的方案数01背包变形。（最后边界条件和至多有些不同其他一样）

最后实现代码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (target < 0) target = -target;
        int sum_nums = 0;
        for(auto num : nums) sum_nums += num;
        if ((sum_nums+target)%2) return 0;
        int nw_target = (sum_nums+target)/2;
        vector<int> dp(nw_target+1, 0);
        dp[0] = 1;
        for(auto num : nums){
            for(int i=nw_target;i>=0;--i){
                if(i>=num) dp[i] += dp[i-num];
            }
        }
        return dp[nw_target];
    }
};

完全背包

题目传送门：322. 零钱兑换 - 力扣（LeetCode）

同上，此题是一个恰好得到n的方案数完全背包变形，求的是最小。

最后实现代码如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,1e9+7);
        dp[0] = 0;
        for(auto coin : coins){
            for(int i=coin;i<=amount;++i){
                dp[i] = min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==1e9+7?-1:dp[amount];
    }
};

变形3

01背包

题目传送门：2742. 给墙壁刷油漆 - 力扣（LeetCode）

这道题简单转换一下其实还是一个01背包问题，只不过最后需要保证付费刷墙的时间要大于等于免费刷墙的墙数。若有n面墙，则：免费刷墙数 = n - 付费刷墙数。

带入前面不等式得：

付费刷墙数 + 付费刷墙时间 >= n

相当于每堵被我们选来付费刷的墙他的所需时间+1，最后需要保证总时间大于等于n的情况下开销尽可能小。

问题成功转变为一个至少变形的01背包问题

最后实现代码如下：

class Solution {
public:
    int paintWalls(vector<int> &cost, vector<int> &time) {
        int n = cost.size();
        vector<int> dp(n + 1, INT_MAX / 2); // 防止加法溢出
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int nw_cost = cost[i], nw_time = time[i]+1;
            for(int j=n;j>=0;--j){
                dp[j] = min(dp[j], dp[max(0, j-nw_time)]+nw_cost);
            }
        }
        return dp[n];
    }
};

可能中间那个max有一点不好理解，此题为min/max模型，如果是方案数模型，则动态规划方程会变为（初始dp[0]=1）：

dp[i] = dp[i] + dp[\max(0,i-c)]

可以想想最极限的情况，就是至少为0的情况下，在该情况下，所有样本都可以选或者不选，只有循环到0并且按照上面这样写才能对至少为0的情况的方案数进行正确的更新。