今天LeetCode的每日一题是分割等和子集，这道题可以看成是一个0-1背包问题。

只是分享一下自己理解的过程，可能表述并不是很清楚，公式的推导就不说了，网上有很多很专业的文章。


0-1背包问题

关于背包问题的定义，网上有很多。

举个列子：

一个小偷拿了一个承重为10kg的背包去商店偷东西，有3种物品供他选择；第一种重1kg，价值6元；第二种重2kg价值10元；第三种重3kg，价值12元。不能重复拿同一种物品，请问小偷如何拿能获取最多的钱？

我们可以使用一个 表格分析一下:

dp[i][j]表示在前0~i种物品中挑选，组成重量为j的组合，最大价值是多少

行代表可选择的物品(1、2、3)，列代表背包容量(kg)，行列相交的值代表可以获取的最大价值(元)

i\j 0 1 2 3 4 5
{1} 0 0 6 6 6 6 6
{1,2} 1 0 6 10 16 16 16
{1,2,3} 2 0 6 10 12 18 22

假设物品种类为n，背包重量为target，将表格转换为一个二维数组dp，

那么最大价值为 dp[n-1][target] = 22

代码实现

分析：

  • i=0时：

    • j = 0 ，dp[0][0] = 0
    • j > 0 ; dp[0][j] = v[i]

  • i >0时，j>=w[i]即背包容量大于i的重量：

    • 选取i，dp[i][j] = v[i] + dp[i-1][j-w[i]]

    • 不选i, dp[i][j] = dp[i-1][j]

  • 取两种情况的较大值


分割等和子集

题目描述

官方题解

理解分析：

代码实现

i\j 0 1 2 3 4 5 6 7 8 9 10 11
(1) 0 true true false false false false false false false false false false
(5) 1 true true false false false true true false false false false false
(11)2 true true false false false true true false false false false true
(5) 3 true true false false false true true false false false true true
  • 1、5、11、5的和是22，所以只要从中取出n个数之和等于11，说明可以被分割。
  • dp[i][j]代表，0-i 的数，可以组和成等于 j ，就位true，不可以就为false。
  • 最终结果就是 dp[len-1][target]。

这里的代码实现，实际上只使用了一个一维数组，使空间复杂度降低，因为分析表格可以知道，d[i][j]的值之和dp[i-1][j]或者dp[i-1][j-w[i]]（即前一行）的值有关。

ps: 其实我有很多地方表述不了很清楚，建议在纸上画表格分析推导一下，然后看下代码手动实现一遍。。

参考链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/