动态规划-背包问题

01背包

二维DP
优点是可以通过回溯拿到最优方案对应的解
递推方程：
f ( n , r e s t ) = { f ( n + 1 , rest ) , rest < w ( n ) ; max ⁡ { f ( n + 1 , rest ) , f ( n + 1 , rest − w ( n ) ) + v ( n ) } , rest ≥ w ( n ) . \begin{equation*} f(n, rest)= \begin{cases} f(n+1,\text{rest}),&\text{rest}<w(n);\\ \max \{f(n+1,\text{rest}), f(n+1,\text{rest}-w(n))+v(n)\},&\text{rest} \ge w(n). \end{cases} \end{equation*} f(n,rest)={f(n+1,rest),max{f(n+1,rest),f(n+1,rest−w(n))+v(n)},​rest<w(n);rest≥w(n).​​
以打表减少递归计算的动态规划初衷出发，我们可以写出以上递推方程。其中$n$表示物品$n$的决策阶段，rest表示这次决策时所剩背包资源容量。
首先创建dp表

import numpy as np
dp = np.zeros((N+1, bag+1))  # 物品0base计数，下标n表示所有决策进行后的边界。

首先对递归边界进行初始化，然后回归计算累加价值即可。
初始化

for rest in range(0, bag+1):
	dp[n, rest] = 0  # 决策边界之外任何剩余空间都无法带来价值

回归计算
从二维递推关系中看出我们需要先计算所有$f(n+1,\ast )$，再计算$f(n,\ast )$，因此我们可以确定内层循环为rest，外层为n。

for n in range(N-1, -1, -1):
	wn = w[n]
	vn = v[n]
	for rest in range(0, bag+1):
		if rest<wn:
			dp[n, rest] = dp[n+1, rest]
		else:
			dp[n, rest] = dp[n+1, rest] if dp[n+1, rest]>(dp[n+1, rest-wn]+vn) else dp[n+1, rest-wn]+vn

返回结果

print(dp[0, bag])  # n=0的决策结束后，dp表中存储的即为给定条件下的最大价值。

滚动dp优化打表维度
优点是可以空间复杂度更低。时间上也可以进行一定优化（不能优化渐进复杂度）。
通过观察递推公式与回归计算，可以发现$n$这个维度可以只存在于循环控制中，在dp中通过时间而非空间存储。
因为内层循环为rest，dp[n, rest]的更新要么依赖dp[n, rest]要么依赖dp[n, rest-wn]。
而$rest\le rest,rest-wn\le rest$，即存在“单调性”。
因此我们在更新$dp[n,res{t}_i]$时只需要确保$dp[n-1,res{t}_j]$，$j\le i$都可被正确检索即可。
所以内层循环rest需要从bag向0步进，每次只更新最大的未更改值。

import numpy as np

dp = np.zeros((bag+1))  # 物品0base计数，下标n表示所有决策进行后的边界。
dp[rest] = 0  # 决策边界之外任何剩余空间都无法带来价值

for n in range(N-1, -1, -1):
	wn = w[n]
	vn = v[n]
	for rest in range(bag, -1, -1):
		if rest>=wn and dp[rest]<(dp[rest-wn]+vn):
			dp[rest] = dp[rest-wn]+vn
print(dp[bag])  # n=0的决策结束后，dp表中存储的即为给定条件下的最大价值。

时间优化版

import numpy as np

dp = np.zeros((bag+1))  # 物品0base计数，下标n表示所有决策进行后的边界。
dp[rest] = 0  # 决策边界之外任何剩余空间都无法带来价值

for n in range(N-1, -1, -1):
	wn = w[n]
	vn = v[n]
	for rest in range(bag, wn-1, -1):
		if dp[rest]<(dp[rest-wn]+vn):
			dp[rest] = dp[rest-wn]+vn
print(dp[bag])  # n=0的决策结束后，dp表中存储的即为给定条件下的最大价值。

网上多数的背包递推方程为：
f ( n , r e s t ) = { f ( n − 1 , rest ) , rest < w ( n ) ; max ⁡ { f ( n − 1 , rest ) , f ( n − 1 , rest − w ( n ) ) + v ( n ) } , rest ≥ w ( n ) . \begin{equation*} f(n, rest)= \begin{cases} f(n-1,\text{rest}),&\text{rest}<w(n);\\ \max \{f(n-1,\text{rest}), f(n-1,\text{rest}-w(n))+v(n)\},&\text{rest} \ge w(n). \end{cases} \end{equation*} f(n,rest)={f(n−1,rest),max{f(n−1,rest),f(n−1,rest−w(n))+v(n)},​rest<w(n);rest≥w(n).​​
他们的递推边界是f(0,rest)，物品1base计数。以从边界向另一个方向推进的思想可以看出这两种方法是等价的。
区别在于可解释性中的决策方向。
假设物品摆放成一行后自左向右以0开始到N的编号。
我的n是自左向右决策时对第n件物品的决策。
传统公式可以看作自右向左进行的决策，这样回归时就是自左向右了，这时边界只能用0存储，因此他们使用1base。

LeetCode416分割等和子集

蛮力递归 36 / 143 个通过的测试用例

class Solution {
public:
    vector<int> nums;
    bool recursive(int index, int bag){
        if (bag<0) return false;
        if(index>=nums.size()){
            return bag==0;
        }
        bool plan0 = recursive(index+1, bag);
        bool plan1 = recursive(index+1, bag-nums[index]);
        return plan0 || plan1;
    }
    bool canPartition(vector<int>& nums) {
        this->nums=nums;
        int sum=0;
        for(const int & num:nums){
            sum += num;
        }
        if(sum%2) return false;
        bool res = recursive(0, sum/2);
        return res;
    }
};

二维DP，且内层循环的边界不够优。$T(n)=O(n\cdot \frac{1}{2}{\sum }_i{\text{nums}}_i)$（327ms）

bool canPartition(vector<int>& nums) {
    int sum=0, n=nums.size();
    sum = accumulate(nums.begin(), nums.end(), 0);
    if(sum%2) return false;
    int bag = sum/2;
    vector<vector<bool>> memo(nums.size()+1, vector<bool>(bag+1,false));
    memo[n][0]=true;
    for(int index=n-1; index>=0; --index){
        for(int rest=0; rest<=bag; ++rest){
            int cur_weight = nums[index];
            if(rest-cur_weight<0){
                memo[index][rest]=memo[index+1][rest];
            }else{
                memo[index][rest]=memo[index+1][rest]||memo[index+1][rest-cur_weight];
            }
        }
    }
    return memo[0][bag];
}

一维DP，最终优化版$T(n)=O({\sum }_j(\frac{1}{2}{\sum }_i{\text{nums}}_i-{\text{nums}}_j))=O((n-1)\cdot \frac{1}{2}{\sum }_i{\text{nums}}_i)$，运行时间更快（35ms），包括内层循环优化与节省内存分配时间。二维版没办法做内循环优化，因为他需要拷贝$n+1$次决策的结果来覆盖初始值。但是他的优点是可以通过回溯获取对应的解。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int bag = accumulate(nums.begin(), nums.end(), 0);
        if(bag%2) return false;
        bag /= 2;
        vector<int> dp(bag+1, 0);
        dp[0]=1;
        for(int i = n-1; i >= 0; --i){
            int wn = nums[i];
            for(int rest=bag; rest>=wn; --rest){
                if(dp[rest-wn]||dp[rest]){
                    dp[rest]=1;
                }
            }
        }
        return dp[bag];
    }
};

多重背包

行展开成01背包即可

完全背包

每种物品的数量不设上限。
LeetCode279完全平方数
朴素三重循环

超时 570 / 589 个通过的测试用例

class Solution {
public:
    int numSquares(int n) {
        int i = 1;
        vector<int> squares;
        while(i*i<=n){
            squares.push_back(i*i);
            ++i;
        }
        vector<vector<int>>dp(squares.size()+1, vector<int>(n+1, INT_MAX));
        dp[squares.size()][0]=0;
        for(i=squares.size()-1; i >= 0; --i){
            int wn=squares[i];
            for(int rest = 0; rest<=n; ++rest){
                dp[i][rest]=dp[i+1][rest];
                for(int k = 1; k*wn<=rest; ++k){
                    if(dp[i+1][rest-k*wn]!=INT_MAX&&dp[i+1][rest-k*wn]+k<dp[i][rest]){
                        dp[i][rest]=dp[i+1][rest-k*wn]+k;
                    }
                }
            }
        }
        return dp[0][n];
    }
};

两重循环版

从以上代码中可以看到，$\text{rest}-k\ast wn<\text{rest}，k>0$。也就是当rest循环是从小到大时，$dp[i][\text{rest}-wn]$其实已经更新完了，而且他自己需要检查所有$k$更大的情况，并将结果保存到自己的位置，因此循环控制$k$可以解除。
即$dp[i][\text{rest}-wn]$在更新的时候检查了
$dp[i+1][\text{rest}-wn-k\cdot wn]+k,k\ge 1:=dp[i+1][\text{rest}-k\cdot wn]+k-1,k\ge 0$
并将其中最小值存储在自己的位置。而$dp[i][\text{rest}]$需要检查的
$dp[i+1][\text{rest}-k\cdot wn]+k,k\ge 0$，
除了$k=0$都已经减1比较过并存放在$dp[i][\text{rest}-wn]$，因此只需要将$dp[i][\text{rest}-wn]+1$即可获得至少选择1项时的最优解。

class Solution {
public:
    int numSquares(int n) {
        int i = 1;
        vector<int> squares;
        while(i*i<=n){
            squares.push_back(i*i);
            ++i;
        }
        vector<vector<int>>dp(squares.size()+1, vector<int>(n+1, INT_MAX));
        dp[squares.size()][0]=0;
        for(i=squares.size()-1; i >= 0; --i){
            int wn=squares[i];
            for(int rest = 0; rest<=n; ++rest){
                dp[i][rest]=dp[i+1][rest];
                if(rest>=wn&&dp[i][rest-wn]!=INT_MAX&&dp[i][rest-wn]+1<dp[i][rest]){
                    dp[i][rest]=dp[i][rest-wn]+1;
                }
            }
        }
        return dp[0][n];
    }
};

滚动DP版

class Solution {
public:
    int numSquares(int n) {
        int i = 1;
        vector<int> squares;
        while(i*i<=n){
            squares.push_back(i*i);
            ++i;
        }
        vector<int>dp(n+1, INT_MAX);
        dp[0]=0;
        for(i=squares.size()-1; i >= 0; --i){
            int wn=squares[i];
            for(int rest = wn; rest<=n; ++rest){
                if(dp[rest-wn]!=INT_MAX&&dp[rest-wn]+1<dp[rest]){
                    dp[rest]=dp[rest-wn]+1;
                }
            }
        }
        return dp[n];
    }
};

LeetCode322零钱兑换
朴素三重循环+回溯法获取优化解

超时 115 / 189 个通过的测试用例
本题超时原因是回溯的复杂度而非三重循环。在满足题意的解足够多时，从回溯中获取最小硬币数的方法就会超时。
追踪数组记录递归树可以保存一个可行解，但是对解的额外约束无法满足。
因此本题需要直接以问题的目标作为优化函数而不是作为完全背包问题间接获取。

class Solution {
public:
    vector<vector<int>> dp;
    int n_coins=INT_MAX, n;
    int coinChange(vector<int>& coins, int amount) {
        n = coins.size();
        dp = vector<vector<int>>(n+1, vector<int>(amount+1, 0));
        for(int i = n-1; i>=0; --i){
            int wn=coins[i]; int vn=coins[i];
            for(int rest = 0; rest<=amount; ++rest){
                dp[i][rest]=dp[i+1][rest];
                for(int k = 1; k*wn<=rest; ++k){
                    if (dp[i][rest]<dp[i+1][rest-k*wn]+k*vn){
                        dp[i][rest]=dp[i+1][rest-k*wn]+k*vn;
                    }
                }
            }
        }
        if(dp[0][amount]!=amount){
            return -1;
        }
        backtrace(coins, 0, 0, amount, amount);
        return n_coins;
    }
    
    inline void backtrace(const vector<int>& coins, int i, int n_coins, int bag, int total){
        if(total==0 && n_coins<this->n_coins){
            this->n_coins = n_coins;
            return;
        }
        if(i==n || bag<0){
            return;
        }
        int wn=coins[i], vn=coins[i];
        for(int k = 0; k*wn<=bag; k++){
            if(dp[i+1][bag-k*wn]+k*vn==total){
                backtrace(coins, i+1, n_coins+k, bag-k*wn, total-k*vn);
            }
        }
    }
};

朴素三重循环+标记法获取优化解

由于优化目标此时是恰好装满，拿到的任意可行解并不满足用币最少的要求。此算法只展示如何通过标记数组拿到一个解的流程。

class Solution {
public:
    vector<vector<int>> dp;
    vector<vector<int>> mark;
    int n_coins=INT_MAX, n;
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end(), less<int>());
        n = coins.size();
        dp = vector<vector<int>>(n+1, vector<int>(amount+1, 0));
        mark = vector<vector<int>>(n+1, vector<int>(amount+1,INT_MAX));
        for(int rest = coins[n-1]; rest<=amount; ++rest){
            mark[n-1][rest] = n-1;
        }
        for(int i = n-1; i>=0; --i){
            int wn=coins[i]; int vn=coins[i];
            for(int rest = 0; rest<=amount; ++rest){
                dp[i][rest]=dp[i+1][rest];
                mark[i][rest]=mark[i+1][rest];
                for(int k = 1; k*wn<=rest; ++k){
                    if (dp[i][rest]<dp[i+1][rest-k*wn]+k*vn){
                        dp[i][rest]=dp[i+1][rest-k*wn]+k*vn;
                        mark[i][rest]=i;
                    }
                }
            }
        }
        if(!amount) return 0;
        if(dp[0][amount]!=amount){
            return -1;
        }
        n_coins = get_solution(mark, amount, coins);
        return n_coins;
    }
    int get_solution(vector<vector<int>> &mark, int bag, vector<int>& coins){
        vector<int>selected(mark.size(), 0);
        for(int i = mark.size()-1; i>=0; --i){
            int wi = coins[i];
            while(mark[i][bag]==i){
                selected[i]++;
                bag-=wi;
            }
        }
        int res = accumulate(selected.begin(), selected.end(), 0);
        return res;
    }
};

记忆化搜索

对于完全背包问题，也可采取记忆化搜索逐个选取的方案求解。区别在于无法确定循环次数。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
    	// 丢掉面值过大的硬币在某些情况下可以优化 但是本题样例没有明显提升
        // sort(coins.begin(), coins.end());
        // auto it = upper_bound(coins.begin(), coins.end(), amount);
        // vector<int>coins_cp=coins;
        // if(it != coins.end()){
        //     int num_candidate = distance(coins.begin(), it);
        //     coins_cp = vector<int>(num_candidate, 0);
        //     copy(coins.begin(), it, coins_cp.begin());
        // }
        // coins = coins_cp;
        vector<int> dp(amount+1, INT_MAX);
        dp[0]=0;
        for (const int &coin:coins){
            if(coin>=dp.size()) continue;
            dp[coin]=1;
        }
        while(true){
            bool better=false;
            for(int rest = amount; rest>=0; --rest){
                for (const int &coin:coins){
                    if(rest>coin&&dp[rest-coin]!=INT_MAX && dp[rest]>dp[rest-coin]+1){
                        better=true;
                        dp[rest] = dp[rest-coin]+1;
                    }
                }
            }
            if(!better || dp[amount]!=INT_MAX) break;
        }
        if(dp[amount]==INT_MAX){
            return -1;
        }else{
            return dp[amount];
        }
    }
};

DP版

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT_MAX);
        dp[0]=0;
        for (const int &coin:coins){
            if(coin>=dp.size()) continue;
            dp[coin]=1;
        }
        for(int i = coins.size()-1; i>=0; --i){
            int wn = coins[i];
            for(int rest=wn; rest<=amount; ++rest){
                if(dp[rest-wn]!=INT_MAX && dp[rest-wn]+1<dp[rest]){
                    dp[rest]=dp[rest-wn]+1;
                }               
            }
        }
        if(dp[amount]==INT_MAX){
            return -1;
        }else{
            return dp[amount];
        }
    }
};

分组背包

每个组限制只能拾取一定数量（至多或恰好k个）的物品
掷骰子等于目标和的方法数
将每个骰子视为一个分组，每个分组必须选一个点数

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = int(1e9+7)
        dp = [[0]*(target+1) for _ in range(n+1)]
        for i in range(1, k+1):
            if i > target:
                break
            dp[n-1][i] = 1
        for i in range(n-2, -1, -1):
            for value in range(target+1):
                for j in range(1, k+1):
                    if value>=j:
                        dp[i][value] = (dp[i][value]+dp[i+1][value-j])%MOD
    
        return dp[0][target]