经典动态规划：子集背包问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典动态规划：子集背包问题

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

滴，学生卡。

[Tokics]

唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。

这句话没读懂啊，为啥会影响之前的其他结果？
为啥原来二维数组不用反向遍历？二维数组不能反过来遍历吧，前一个值都没有算出来，反过来不就不能利用上一个计算出来的值了吗？

[chase4ever]

这个要慢慢品，我理解了好久才悟到。

1. 为什么不能正向遍历？因为外层遍历的是物品，0-1背包问题，一个物品只能选择一次，就是说，如果j正向遍历，容量从小到大可能多次选择这个品。
   2.反向遍历，前面的数据都没计算，为什么j反向遍历正确？ 因为在计算dp[i][j]的时候，使用的是dp[i-1][j-v]的数据，即：只考虑0~i-1这么多物品的情况下的结果。这些都是完全计算过了的，反向遍历没有问题，且，反向遍历可以保证在j之前的容量里，一定没有考虑过这个物品。也就是说，当前可以决策是否装入i这个物品，是因为在这之前的容量没有考虑过是否装入i，保证i只能最多装入1次。

[Pandede]

dp[j] = dp[j] or dp[j - nums[i]]

關鍵or後面的判斷式，如果一維數組時還是用正向遍歷的話，dp[j]前面的已經更新成dp[i][j]而不是dp[i-1][j]
二維數組可以正向遍歷是因為dp[i][j]是從dp[i-1][j]更新而來的，所以沒有問題。
如果還是想用正向遍歷的話，可以改成：

for i in range(n):
    prev = dp.copy()
    for j in range(sum+1):
        if j - nums[i] >= 0:
            dp[j] = prev[j] or prev[j - nums[i]]

但這樣就需要用多一倍的記憶體了。

[tiertie]

唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。

这句话没读懂啊，为啥会影响之前的其他结果？ 为啥原来二维数组不用反向遍历？二维数组不能反过来遍历吧，前一个值都没有算出来，反过来不就不能利用上一个计算出来的值了吗？

qs,我也想知道

[labuladong]

关于空间优化的问题，在网站搜索「对动态规划进行降维打击」这篇文章，有详细解释。

[david820505]

個人理解 不確定是不是正確 :)

觀察2D 是依據前一排 i-1 得出的 (like dp[i-1][j] ),
而第一排其實是 Base case ( dp[0: i][0] = true, dp[0][1: halfSum] = false) 所以才能得出下一排的解答.

轉成1D 要反轉是因為 dp[ j - nums[i-1]],
原本2D要取 "上一排" 比 j 小的值. 但是1D如果從 j =1開始, 1D array前方的值就會被改變，後方再取 j - nums[i-1] 就變成 updated過的值, 而從後方開始就可以避免這個問題.

[Tokics]

还是没理解。尝试按之前的遍历方向那篇博文 https://labuladong.gitee.io/algo/3/24/71/

画了矩阵图，dp[i][j] 来自于 dp[i-1][j]和 dp[i-1][j-nums[i]]
，那篇博文dp[i][j]来自dp[i-1][j] 和dp[i-1][j-1]、dp[i][j-1]，博文说要正向遍历
因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案 dp[m][n]。

我画了图，这道题的情况base case 和它相同，方向也一致，为什么这个就是从右到左了，画图的时候怎么区别这种情况呢？

[zhongweiLeex]

还是没理解。尝试按之前的遍历方向那篇博文 https://labuladong.gitee.io/algo/3/24/71/

画了矩阵图，dp[i][j] 来自于 dp[i-1][j]和 dp[i-1][j-nums[i]] ，那篇博文dp[i][j]来自dp[i-1][j] 和dp[i-1][j-1]、dp[i][j-1]，博文说要正向遍历 因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案 dp[m][n]。

我画了图，这道题的情况base case 和它相同，方向也一致，为什么这个就是从右到左了，画图的时候怎么区别这种情况呢？

注意： 这个方向不是固定的 一定要弄清楚 当前的状态依赖于从哪个方向传递过来的前一个状态， 比如 如果 i状态依赖于 从 m方向传递过来的 这种情况你所说的 每一步迭代依赖位置就不一样了

[Tokics]

@zhongweiLeex 我判断方向错了吗？我画出来两个方向都是左上到右下。区别在于倾斜度不同，为什么一个需要反方向遍历，一个不用呢？

[zhongweiLeex]

@zhongweiLeex 我判断方向错了吗？我画出来两个方向都是左上到右下。区别在于倾斜度不同，为什么一个需要反方向遍历，一个不用呢？

建议再读一下，东哥公众号 labuladong 的 动态规划答疑这篇文章， 关于dp方向，讲的蛮清楚的。！

[lee666-lee]

@Tokics 楼上大佬们解释得很清晰啦，我再来补充点看会不会更具体些？

1.先看原来2D情况，dp[i][j]的值，都是仅依靠上一行dp[i-1][...]得出的。意思是我们要算当前dp[i]行的值，仅需要上一行dp[i-1]就好。所以可以将其转化为：原地更新1D数组问题；

2.现在考虑降为1D，定义该1D数组为int[] dp。回忆原来2D情况，dp[i][j]的值都是依靠“其正上方的值dp[i-1][j]+左上方的值dp[i-1][j-nums[i]]”来更新。那么如果对1D进行正向遍历即从dp[0]->dp[n-1]填充，对于某一位例如dp[cur]的更新，势必会用到dp[pre]（pre<cur），因为是正向遍历，那么dp[pre]在当前轮次已经被更新过了，当在这种情况下计算的dp[cur]肯定不正确（其实说白了，就相当于2D情况下，使用了同一行的值。例如使用dp[i][j-nums[i]]来更新dp[i][j]）；

3.现在解释对1D数组进行反向遍历即从dp[n-1]->dp[0]填充。同样，对于某一位例如dp[cur]的更新，势必会用到dp[pre]（pre<cur）。但注意，因为是从后往前进行遍历的，此时dp[pre]在当前轮次未被更新，所以就相当于2D情况下使用的上一行的值，这样计算就是正确的了。

[labuladong]

@lee666-lee 总结的很正确👍

[kuangkuangkuangha]

@labuladong 我觉得动态规划问题用递归（自顶而下）的时间复杂度是不是天生要比迭代（自底而上）高啊？（递归在参数传递的时候会有额外的时空开销），或者这些开销相对于整体可以忽略不计？
这个想法来源是东哥在前几节动态规划子序列问题，我解题时的个人感觉，字符串其实可以穿拷贝的，oj也是能通的过，当然传引用的效率更高这是可以理解的。
🙏🙏🙏

在这题中我也有同样的感觉（这个oj超时了）
我个人感觉这个问题不能用备忘录优化的（菜狗）
416 c++

class Solution {
public:

   // 定义dp为在前i个数据中挑数累加, 直到结果等于总和的一半
  // sum从0开始选数求和，直到等于总和的一半
    bool dp(vector<int>& nums, int i, int sum, int cap ）// cap为总和的一半
    {
        if(sum == cap)
            return true;

        if(i == -1)
            return false;

        return dp(nums, i-1, sum, cap)||dp(nums, i-1, sum+nums[i], cap);
    }

    bool canPartition(vector<int>& nums) {
        int cap = accumulate(nums.begin(), nums.end(), 0);
        if(cap%2 == 1)
            return false;

        return dp(nums, nums.size()-1, 0, cap/2);  
    }
};

[kuangkuangkuangha]

PS：再引申一个问题，动态规划能用递归做应该也能用迭代做，所以会不会有哪些情况或特殊的问题下这两种方法有优劣之分呢？
求东哥解惑🙏

[kuangkuangkuangha]

@labuladong 捞一捞，大佬

[labuladong]

@kuangkuangkuangha 首先给你的思考点赞~

1、你给出的这个解法，本质上不是动态规划思路，而是回溯算法思路，暴力尝试所有可能的累加和，所以当然会超时。

动态规划的关键在于「状态转移方程」，即如何通过若干个已计算出的「状态」推导出未计算的「状态」，在这个推导「状态」的过程中，可能存在重复计算「状态」的情况（重叠子问题），需要备忘录技巧消除冗余计算。进一步，备忘录可以改造成 dp 数组，用非递归的方式进行状态转移，也就是自底向上的动态规划解法。

那么看看你给出的代码，虽然函数名字叫 dp，但你是否能够找到这个函数在递归过程中在不断变化的「状态」？也许你会说参数 i 和 sum 在变化，可以把他们看做「状态」，嗯，这没问题，但问题是你是否能够通过已经计算出来的「状态」推导出未计算的状态？答案是不行。

比如就按照你的定义，比如说 dp(i) == false，那我知道 nums[0..i] 不能凑出目标和 cap，但这个结论能复用吗？你能通过 dp(i) == false 推出 dp(i + 1) 等于多少吗？不能，还得老老实实从头穷举 nums[0..i+1] 能不能凑出 cap。

所以，你的这个解法思路是回溯算法，改写成如下形式看起来更明显：

bool backtrack(vector<int>& nums, int i, int trackSum, int cap ) {
    if(trackSum == cap)
        return true;

    if(i == -1)
        return false;

    // 做选择
    trackSum += 0;
    backtrack(nums, i - 1, trackSum, cap)
    // 撤销选择
    trackSum -= 0;

    // 做选择
    trackSum += nums[i];
    backtrack(nums, i - 1, trackSum, cap);
    // 撤销选择
    trackSum -= nums[i];
}

2、动态规划用于优化暴力穷举解法所用的备忘录 memo 中的内容其实就是 dp 数组的内容，大部分情况他们的理论效率相同，至于你说的递归参数的问题，从 Big O 表示法 的角度来看是可以忽略不计的。特殊情况是有的，比如改成迭代之后可以应用 空间压缩技巧 优化空间复杂度；再比如状态转移设计不合理的情况下，可能你只能写出递归解法，却无法写出迭代解法。

以上是我个人的一些理解，我觉得你提出的这个问题很有价值，后续考虑专门写篇文章写一写动态规划和回溯算法在思路上的区别。如果你还有什么问题，欢迎继续和我探讨~

[lhcezx]

贴一个自顶向下带个备忘录C++

 bool dp(vector<int>& nums, int i, int size) {
        // base case
        int j = size;
        if (size == 0) return true;                  //  背包被装满了，返回true
        if (i == -1) return false;                   //  没有可以选择的数字，因此不可能装满
        if (memo[i][j] != -1) return memo[i][j];
        if (size - nums[i] >= 0) {
            return memo[i][j] = dp(nums, i - 1, size) || dp(nums, i - 1, size - nums[i]);       //  dp(nums, i - 1, size)：判断不放nums[i]能否将size装满; dp(nums, i - 1, size - nums[i]) 放nums[i]的话判断是否在[1, i - 1]这些数字中将size - nums[i]装满
        } else {
            return memo[i][j] = dp(nums, i - 1, size);
        }
    }

    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (auto num: nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;                         //  无法分割
        int size = sum / 2;
        memo.assign(n, vector<int> (size + 1, -1));   //  重量从0到sum / 2;
        return dp(nums, n - 1, sum / 2);            
    }
};

[guqihao-7]

记忆化搜索Java版本：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) return false;
        memo = new Boolean[sum / 2 + 1][nums.length];
        return process(nums, sum / 2, 0);
    }

    Boolean[][] memo;

    public boolean process(int[] nums, int bag, int index) {
        if (index < 0 || index >= nums.length) {
            return false;
        }

        if (bag == 0) {
            return true;
        } else if (bag < 0) {
            return false;
        }

        if (memo[bag][index] != null) {
            return memo[bag][index];
        }

        memo[bag][index] = process(nums, bag - nums[index], index + 1)
                || process(nums, bag, index + 1);
        return memo[bag][index];
    }
}

[6VastUniverse]

我觉得递归和递推的区别有两个：

1. 递归不用考虑顺序，如果加上备忘录，就会把每一个算一遍，不会漏也不会重复；
2. 递归空间占用大，容易运行错误，也就是“爆栈”。

[zput]

二维压缩到一维，一般是指保留一行，去掉其他行。
》当前的（i，j）只利用到了 上一行的 （i-1，j）与（i-1, j-num[j]）

假设 j为5， j-num[j]为3， 则
第i-1行：x x x 3 x 5
第i行： x x x x x x

在一维的情形下：所以如果j是从0向上增长的话，第i-1行的3已经更新了（被第i行） ， 等到计算第i行的5
用到的（i-1, j-num[j]）其实已经变为（i, j-num[j]）

综上所述，从大到小遍历才不会出问题。

[Xingyue0310]

Python解法

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        Sum = sum(nums)
        if Sum % 2 != 0:
            return False
        Sum = Sum // 2 # bag capacity
        
        # 对于前i个物品，背包的容量为j
        # dp[i][j] = true能恰好装满，false不能恰好装满
        dp = [[False for _ in range(Sum+1)] for __ in range(n+1)]
        # base case：背包容量为0时，什么都不装也已经装满了
        for i in range(n+1):
            dp[i][0] = True
        
        # 对于每一个新加入的元素nums[i-1]循环
        for i in range(1, n+1):
            # 对于1到Sum中每一个背包容量，判断能否正好装满
            for j in range(1, Sum+1):
                # 背包容量不足，不装入第i个物品
                # 此时能否装满的判断，等于没有加入元素nums[i-1]时的状态
                if j - nums[i-1] < 0:
                    dp[i][j] = dp[i-1][j]
                # 容量足够，对nums[i-1]有两个选择：
                # 装入nums[i-1]，能否恰巧装满取决于dp[i-1][j-nums[i-1]]的状态
                # 不装nums[i-1]，能否装满取决于dp[i-1][j]的状态
                else:
                    dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
        return dp[n][Sum]

[yonggui-yan]

打卡
01， 背包的应用

[process-sk]

dp[i][j] = x j是背包的剩余重量

[GXhunter]

个人认为在定义状态的时候，n定义为使用前个元素（包含），这样能直接使用nums[j] 不用nums[j-1]会直观一点，缺点就是表达不了没有元素的情况，因为即便n取0也有一个元素。
所以basecase写法不一样，要判断只有一个元素的情况

class Solution {
   public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
//        dp[i][j]: 使用 [0:j]个元素是否能够拼出sum
        boolean[][] dp = new boolean[sum + 1][n];
        for (int i = 0; i <= sum; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
//                    背包为空，多少元素都可以装满
                    dp[i][j] = true;
                    continue;
                }
                if (j == 0) {
//                    只有一个元素,如果刚好跟背包一样大小，就能填充
                    dp[i][j] = i == nums[j];
                    continue;
                }
                if (i >= nums[j]) {
                    dp[i][j] = dp[i][j - 1] || dp[i - nums[j]][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[sum][n - 1];
    }
}

[reozong]

请教东哥，根据dp数组的定义，是不是dp[1...n][sum]只要有一个true就可以提前结束遍历了，不需要一直遍历完最后取dp[n][sum]？

[labuladong]

我认为你说的没错，按照定义确实是这样的。我尝试添加了这样一段代码，也可以通过所有测试用例：

            if (j == sum && dp[i][j] == true) {
                return true;
            }

[EyeDroplyq]

打卡

[chiao666]

请问这段python代码为何不行啊，调试中发现，dp[..][sum2]已经出现了True，但是没有return:
'''
def canPartition(self, nums: List[int]) -> bool:
sum0=sum(nums)
if sum0%2 != 0:
return False
else:
sum2=int(sum0/2)
#然后就是判断一下能够找到一个组合使得和为sum2
#dp[i][j]对于[..i-1]个物品，背包容量为j时，可以将背包放满，保证i=0时，dp为False，j=0时，dp是True
#目标是dp[...n][sum2]中是否有True
n=len(nums)
dp=[[False]*(sum2+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0]=True
for i in range(1,n+1):
for j in range(1,sum2+1):
if dp[i][sum2]:
return dp[i][sum2]
#考虑nums[i-1]太大不能放的情况：
if j-nums[i-1]<0:
dp[i][j]=dp[i-1][j]
#考虑第i-1个物品是否放进去，不放的话，当前状态能否填满，取决于之前转态，有没有这个i-1一样
#放进去的话，就取决于，上一个dp【i-1】以及上一个容量问题
else:
dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i-1]]
return False
'''

[chiao666]

抱歉回复错了！

[chiao666]

请问这段python代码为何不行啊，调试中发现，dp[..][sum2]已经出现了True，但是没有return:

    def canPartition(self, nums: List[int]) -> bool:
        sum0=sum(nums)
        if sum0%2 != 0:
            return False
        else:
            sum2=int(sum0/2)
        #然后就是判断一下能够找到一个组合使得和为sum2
        #dp[i][j]对于[..i-1]个物品，背包容量为j时，可以将背包放满，保证i=0时，dp为False，j=0时，dp是True
        #目标是dp[...n][sum2]中是否有True
        n=len(nums)
        dp=[[False]*(sum2+1) for _ in range(n+1)]
        for i in range(n+1):
            dp[i][0]=True
        for i in range(1,n+1):
            for j in range(1,sum2+1):
                if dp[i][sum2]:
                    return dp[i][sum2]
                #考虑nums[i-1]太大不能放的情况：
                if j-nums[i-1]<0:
                    dp[i][j]=dp[i-1][j]
                #考虑第i-1个物品是否放进去，不放的话，当前状态能否填满，取决于之前转态，有没有这个i-1一样
                #放进去的话，就取决于，上一个dp【i-1】以及上一个容量问题
                else:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i-1]]
        return False

[chiao666]

我哈皮了，判断放后面才对

[shiboys]

「如果 j - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。」这句话特别不好理解，可能需要借助具体的例子。如果换成 「重量为 j-nums[i-1] 的背包可能更好理解」，(注意，此时的 j-nums[i-1] 和 j 都不是 sum，也就是当前的 j 不是满足题目要求的 sum )

[learn2phd]

最后那个反向遍历，假设现在遍历到nums的i个，dp[j]的更新可能需要dp[j-nums[i]]。如果从前向后遍历sum的值的话，此时dp[j-nums[i]]已经不是dp[i-1][j-nums[i]]，而是dp[i][j-nums[i]]了。这应该就是以免之前的结果影响其他的结果。

[zhengheng36]

在文章最后'时间复杂度 O(n*sum)'中 ‘n*sum' 是typo？

[zhengheng36]

可能是为了给*加上转义字符，多了一个\

[realRuiGuo]

// 严格按照0-1背包定义也能解决。dp数组含义是能放入的最大重量，如果dp[n][w]重量刚好为总和的一半，就表示能分成两组满足各一半。
class Solution {
public:
bool canPartition(vector &nums) {
int sum = 0;
int n = nums.size();
for (auto &item: nums) {
sum += item;
}
if (sum % 2 != 0) {
return false;
}
int w = sum / 2;
vector dp(n + 1, vector(w + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (j - nums[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j - nums[i - 1]] + nums[i - 1], dp[i - 1][j]);
}
}
}
return (dp[n][w] == w);
}
};