初始化
求最优解的背包类型题目中，有两种类似的问法。一种是问“恰好装满背包”的最优解，有的只要求“不超过背包容量即可”。
如果是要求恰好装满的问法时候，那么在初始化时候只有F[0]被初始化为0,其他的状态都应该为未定义状态-INF。如果是后者的问法时，应该将F[0…V]全部初始化成0。可以这样理解：初始化的F数组实际上就是什么都不放的情况下的合法状态，在第一种问法下很明显只有F[0]才满足什么都不装的情况下被“装满”，而后者的问法没有要求必须把背包装满，所以什么都不装也是合法的！可以将这个初始化技巧推广到其它类型的背包问题！
0-1 背包
题目：
有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。
基本思路：
F[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：F[i,v]=max{F[i−1,v],F[i−1,v−Ci]+Wi}
然后根据这个方程便可以写出伪代码，具体代码最好根据不同题目具体要求来写，过度依赖源码很容易犯错。
F[0, 0...V] <- 0
for i <- 1 to N
for v <- Ci to V
F[i, v] <- max(F[i-1, v], F[i-1, v-Ci] + Wi)
优化空间复杂度：
其实可以省去状态里面的一维。具体原理如下：F[i, v]是由F[i-1, v]和F[i-1, v-Ci]两个子问题递推而来，所以只需在主循环中以 v <- V…Ci的方式来递推的话，就能够保证使用的是上一组的F[v]，F[i-1]。具体伪代码如下：
F[0...V] <- 0
for i <- 1 to N
for v <- V to Ci
F[v] <- max(F[v], F[v-Ci] + Wi)
当f(i,j) 只和f(i-1,x)相关时，可以用滚动数组优化空间。类似这样
class Solution:
def canPartition(self, nums: List[int]) -> bool:
totalSum = sum(nums)
if totalSum % 2 == 1:
return False
val = int(totalSum / 2)
dp = [False for _ in range(val + 1)]
dp[0] = True
for i in range(1, len(nums) + 1):
f = [False for _ in range(val + 1)]
for j in range(val + 1):
f[j] = dp[j] or (dp[j - nums[i - 1]] if j >= nums[i - 1] else False)
dp = f
return dp[val]
这里因为x<=j，可以倒序而不用滚动数组，不过看起来滚动数组应用场景更多，不会限制x<=j
Bottom-up:
Solve subproblems whose solution are not necessary for the solving the original problem.
Top-down: Solve common subproblems more than once.
ALGORITHM MFKnapsack(i, w)
if K[i,w] < 0 //if subproblem K(i, w) hasn’t been solved yet.
if w < wi
value = MFKnapsack(i – 1, w)
else
value =max (MFKnapsack(i – 1, w),
v[i] + MFKnapsck( i – 1, w –wi))
k[i, w] = value
return k[i, w]
Java实现代码
public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; j++) {
if (j >= w) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}
public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = W; j >= 1; j--) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[W];
}
无法使用贪心算法的解释
0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.
| id | w | v | v/w |
|---|---|---|---|
| 0 | 1 | 6 | 6 |
| 1 | 2 | 10 | 5 |
| 2 | 3 | 12 | 4 |
变种
完全背包：物品数量为无限个
多重背包：物品数量有限制
多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
其它：物品之间相互约束或者依赖
related problem
划分数组为和相等的两部分
416. Partition Equal Subset Sum (Medium)
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
可以看成一个背包大小为 sum/2 的 0-1 背包问题。
public boolean canPartition(int[] nums) {
int sum = computeArraySum(nums);
if (sum % 2 != 0) {
return false;
}
int W = sum / 2;
boolean[] dp = new boolean[W + 1];
dp[0] = true;
//Arrays.sort(nums); 这里并不需要排序
for (int num : nums) { // 0-1 背包一个物品只能用一次
for (int i = W; i >= num; i--) { // 从后往前，先计算 dp[i] 再计算 dp[i-num]
dp[i] = dp[i] || dp[i - num];
}
}
return dp[W];
}
private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
改变一组数的正负号使得它们的和为一给定数
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
该问题可以转换为 Subset Sum 问题，从而使用 0-1 背包的方法来求解。
可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)
因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。
public int findTargetSumWays(int[] nums, int S) {
int sum = computeArraySum(nums);
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int W = (sum + S) / 2;
int[] dp = new int[W + 1];
dp[0] = 1;
// Arrays.sort(nums); 这里并不需要排序
for (int num : nums) {
for (int i = W; i >= num; i--) {
dp[i] = dp[i] + dp[i - num];
}
}
return dp[W];
}
private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
DFS 解法：
public int findTargetSumWays(int[] nums, int S) {
return findTargetSumWays(nums, 0, S);
}
private int findTargetSumWays(int[] nums, int start, int S) {
if (start == nums.length) {
return S == 0 ? 1 : 0;
}
return findTargetSumWays(nums, start + 1, S + nums[start])
+ findTargetSumWays(nums, start + 1, S - nums[start]);
}
完全背包
题目：
有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是Ci，得到的价值是Wi。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
基本思路：
一种最容易想到的思路就是用01背包的思路来求解，状态定义与01背包一样。方程为：F[i,v]=max{F[i−1,v−kCi]+kWi|0≤kCi≤v}。
k表示第i中物品选多少个。可以将伪代码描述如下。
不好的解法
F[0, 0...V] <- 0
for i <- 1 to N
for v <- Ci to V
for k <- 0 to V/Ci
F[i, v] <- max(F[i-1, v], F[i-1, v-k*Ci] + k*Wi)
优化后
F[0...V] <- 0
for i <- 1 to N
for j <- Ci to V
F[j] <- max(F[j], F[j - Ci] + Wi)
以上是重量迭代在里面，因此比如[1,2,3]组合，每个是1.。2.。3.。
也可以重量在外面，因此比如[1,2,3]组合，每个是1/2/3… 就是没有严格顺序，参考找零钱里，[1,2,5]和[5,2,1]是否算一种，如果算一种，就重量在里面，否则就在外面。
related problem
字符串按单词列表分割
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。
0-1 背包和完全背包在实现上的不同之处是，0-1 背包对物品的迭代是在最外层，而完全背包对物品的迭代是在最里层。
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) { // 完全一个物品可以使用多次
int len = word.length();
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
找零钱的方法数
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
题目描述：给一些面额的硬币，要求用这些硬币来组成给定面额的钱数，并且使得硬币数量最少。硬币可以重复使用。
- 物品：硬币
- 物品大小：面额
- 物品价值：数量
因为硬币可以重复使用，因此这是一个完全背包问题。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
dp = [amount + 1 for _ in range(amount + 1)]
dp[0] = 0
for i in range(1, amount + 1):
for _, coin in enumerate(coins):
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
print(dp)
if dp[amount] <=amount:
return dp[amount]
else:
return -1
组合总和
377. Combination Sum IV (Medium)
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
完全背包。
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] maximum = new int[target + 1];
maximum[0] = 1;
Arrays.sort(nums);
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length && nums[j] <= i; j++) {
maximum[i] += maximum[i - nums[j]];
}
}
return maximum[target];
}
多重背包
题目：
有N种物品和一个容量为V的背包。第i种物品最多有Mi件可以用，每件耗费的空间是Ci，价值是Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
related problem
01 字符构成最多的字符串
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0"
这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。
public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) { // 每个字符串只能用一次
int ones = 0, zeros = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
背包九讲深入
基础背包
ZeroOnePack
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);
CompletePack
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
MultiplePack
多重背包: 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
参考 仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
//amount是数量
procedure MultiplePack(cost,weight,amount)
//数量*成本 > 总容量，变成完全背包形式
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
//一个物品分词若干个物品，每个物品系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
混合三种背包
01背包与完全背包的混合
考虑到在P01和P02中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。伪代码如下：
for i=1..N
if 第i件物品属于01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品属于完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
再加上多重背包
如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。
当然，更清晰的写法是调用我们前面给出的三个相关过程。
for i=1..N
if 第i件物品属于01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品属于完全背包
CompletePack(c[i],w[i])
else if 第i件物品属于多重背包
MultiplePack(c[i],w[i],n[i])
二维费用的背包问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。
物品总个数的限制
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
分组的背包问题
问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}
使用一维数组的伪代码如下：
for 所有的组k
for v=V..0
for 所有的i属于组k
f[v]=max{f[v],f[v-c[i]]+w[i]}
有依赖的背包问题
我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应的最大价值f’[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费用为c[i]+k的物品的价值为f’[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为V-c[i]+1个物品的物品组，就可以直接应用P06的算法解决问题了。
总结
01/有序无序完全背包
01背包d[i][j]代表表示前i件物品恰放入一个容量为j的背包可以获得的最大价值 空间优化后d[i]代表容量为i获得最大值， 遍历时需要物品在外层从小到大，容量在里层，从大到小，避免d[j-w]取的是d[i][j-w]，应该是d[i-1][j-w],可以画二维图看出来。
完全背包在于物品使用无限，但求时有两种，一种是[1,2], 其中[1,1,2]和[2,1,1]是两种，这种需要容量在外层从小到大，物品在里层从小到大，
比如
for i in range(1, amount + 1):
for coin in coins:
if i >= coin:
dp[i] += dp[i - coin]
另一种是[1,1,2]和[2,1,1]算一种，无序完全背包。这种就需要物品在外层从小到大，容量在里层从小到大。一般都为第一种，也更符合dp的原则。比如求硬币的组合数
严格要求211和121都一样，有个顺序的。必须2在前这样。 就把物品迭代放外层。这种就是对物品有严格的顺序然后达到去重的目的的。因此这里要排序，先放小的，不排序也没关系的
Leetcode / 力扣
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0 for _ in range(amount + 1)]
dp[0] = 1
for c in coins:
for k in range(max(1, c), amount + 1):
dp[k] += dp[k - c]
return dp[amount]
求组合数
如果是多个数里判断能否k个数和为target，用回溯。
如果是不限制k个数，01背包或者完全背包。
01背包求和为target的组合数
def combinationSum3(self, nums: List[int], target: int) -> int:
'''
01背包的组合求和。
'''
dp = [0 for _ in range(target + 1)]
dp[0] = 1
mod = 10**9+7
nums.sort()
for num in nums:
for i in range(target, 0, -1):
if i >= num:
dp[i] += dp[i-num]
dp[i] %= mod
else:
break
print(dp)
return dp[target]
完全背包求和为target的组合数
以下是不同顺序算多种的，比如[1,2]和[2,1]算两种。
def combinationSum4(self, nums: List[int], target: int) -> int:
'''
完全背包的组合求和。
'''
dp = [0 for _ in range(target + 1)]
dp[0] = 1
mod = 10**9+7
nums.sort()
for i in range(1, target + 1):
for num in nums :
if i >= num:
dp[i] += dp[i-num]
dp[i] %= mod
print(dp)
return dp[target]
以下是不同顺序算1种的，比如[1,2]和[2,1]算1种。
def combinationSum5(self, nums: List[int], target: int) -> int:
'''
完全背包的组合求和。
'''
dp = [0 for _ in range(target + 1)]
dp[0] = 1
mod = 10**9+7
nums.sort()
for num in nums:
for i in range(1, target + 1):
if i >= num:
dp[i] += dp[i-num]
dp[i] %= mod
# print(dp)
print(dp)
return dp[target]
背包问题思路
那么什么样的问题可以被称作为背包问题？换言之，我们拿到题目如何透过题目的不同包装形式看到里面背包问题的不变内核呢？
我对背包问题定义的理解：
给定一个背包容量target，再给定一个数组nums(物品)，能否按一定方式选取nums中的元素得到target
注意：
1、背包容量target和物品nums的类型可能是数，也可能是字符串
2、target可能题目已经给出(显式)，也可能是需要我们从题目的信息中挖掘出来(非显式)(常见的非显式target比如sum/2等)
3、选取方式有常见的一下几种：每个元素选一次/每个元素选多次/选元素进行排列组合
那么对应的背包问题就是下面我们要讲的背包分类
看有几个变化的变量，变量都可以作为DP的状态，然后DP的值也是一个变量，往往就是题目所求。
如果递推时，是依赖左上或者右下部分，比如dp(i,j)依赖了dp(i-1,j-1)这样，则一般需要通过倒序体积来空间优化，外层是物品，里程是体积倒序，如果还有第三维，第三维也倒序。比如题目3082. 求出所有子序列的能量和
否则可以直接正序。
用回溯思考状态转移的好处，可以避免讨论复杂和式，直接得到化简后的结果。
先记忆化搜索，表示选或者不选，然后到正推DP， 空间优化。
背包问题分类
常见的背包类型主要有以下几种：
1、0/1背包问题：每个元素最多选取一次
2、完全背包问题：每个元素可以重复选择
3、组合背包问题：背包中的物品要考虑顺序
4、分组背包问题：不止一个背包，需要遍历每个背包
而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
1、最值问题：要求最大值/最小值
2、存在问题：是否存在…………，满足…………
3、组合问题：求所有满足……的排列组合
模板
首先是背包分类的模板：
1、0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
2、完全背包：外循环nums,内循环target,target正序且target>=nums[i];
3、组合背包：外循环target,内循环nums,target正序且target>=nums[i];
4、分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板
然后是问题分类的模板：
1、最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
| 2、存在问题(bool)：dp[i]=dp[i] | dp[i-num]; |
3、组合问题：dp[i]+=dp[i-num];
分组背包
class DPPack:
def example(self, target = 30):
dp = [0 for _ in range(target + 1)]
dp[0] = 1
'''
背包问题
cost: 费用, 重量, 体积
value: 价值
amount: 多重背包时每个物品的数量上限
'''
def zeroOnePack(dp, target, cost, value):
for v in range(target, cost - 1, -1):
dp[v] = max(dp[v], dp[v - cost] + value)
def completePack(dp, target, cost, value):
for v in range(cost, target + 1, 1):
dp[v] = max(dp[v], dp[v - cost] + value)
def multiplePack(dp, target, cost, value, amount):
if cost * amount >= target:
completePack(cost, value)
k = 1
while k < amount:
zeroOnePack(cost * k, value * k)
amount -= k
k *= 2
zeroOnePack(cost * amount, value * k)
初始化
最值问题, 最终dp[j]代表体积恰好为j时的价值极值。
dp[0] = 0, 其他float('inf')或者float('-inf')
存在问题
dp[0] = True, 其他False
组合树问题
dp[0] = 1, 其他为0
常见变形
- 至多装target, 求方案数/最大价值和
- 至少装target, 求方案数/最大价值和
- 恰好装target, 求方案数/最大价值和/最小价值和
比如 494. 目标和 在nums数组里选几个元素，使它们和为capacity，求方案数。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
import functools
capacity = (sum(nums) + target)
if capacity < 0 or capacity % 2 == 1:
return 0
capacity //= 2
'''
记忆化搜索方法
'''
@functools.lru_cache(None)
def f(i, s):
if i == 0:
'''
至多装capacity, 求方案数/最大价值和。
则这里应该是return 1， 不管s的值。
至少装capacity, 这里应该是return 1 if s <= 0 else 0
'''
return 1 if s == 0 else 0
v = nums[i - 1]
# don't select
res = f(i - 1, s)
# select.
if s - v >= 0: #至少装capacity时，这里不能有这个判断。
res += f(i - 1, s - v)
return res
ans = f(len(nums), capacity)
f.cache_clear()
# return ans
'''
至多装capacity, 求方案数/最大价值和。
则这里应该是dp都是1，作为dp[i][j] i=0时，都为1，想不通可以从记忆化搜索对应过来就知道了,
记忆化里的i=0就是这里的初始状态
'''
dp = [0] * (capacity + 1)
dp[0] = 1
for v in nums:
'''
#至少装capacity时，这里应该是
for c in range(capacity, - 1, -1),
需要到0，可以理解为，当target为0时，一共有2**n种方案，这样到0才可以满足这个条件。
当c>=target了，则前面的都可以选或者不选
'''
for c in range(capacity, v - 1, -1):
dp[c] += dp[c - v]
return dp[capacity]
初始化边界问题
\- 求max/min的模型里：
- 求体积`恰好`为j：
- 求max, f = 【0】+【-inf】*t
- 求min, f = 【0】+【inf】*t
- 最终f【j】代表体积恰好为j时的价值极值。
---
- 求体积`至多`为j时:
- f【0】 = 【0】+【0】*t (max/min)
- 最终f【j】代表体积`至多`为j时的价值极值
---
- 求体积`至少`为j时:
- f【0】 = 【0】+【0】*t (max/min)
- 同时遍历体积需要修改循环下界v->0、转移需要修改为从max(0,j-v),即
`for j in range(self.vol, -1, -1):f【j】 = merge(f【j】, f【max(j - v,0)】 + w) # 01背包`
`for j in range(self.vol+1):f【j】 = merge(f【j】, f【max(j - v,0)】 + w) # 完全背包`
- 最终f【j】代表体积`至少`为j时的价值极值
\---
\- 求方案数的模型里（一般要取模）:
- 求体积`恰好`为j：
- 求max, f = 【1】+【0】*t
- 最终f【j】代表体积恰好为j时的方案数。
---
- 求体积`至多`为j时:
- f = 【1】+【1】*t
- 最终f【j】代表体积`至多`为j时的方案数。
---
- 求体积`至少`为j时:
- f = 【1】+【0】*t
- 同时遍历体积需要修改循环下界v->0、转移需要修改为从max(0,j-v),即
`for j in range(self.vol, -1, -1):f【j】 += f【max(j - v,0)】 # 01背包`
`for j in range(self.vol+1):f【j】 += f【max(j - v,0)】 # 完全背包`
- 最终f【j】代表体积`至多少`为j时的方案数
有至多至少同时出现的好题目！这里的profit和人数看做体积，人数为至多，profit为至少。是个同时有至多、至少的好题目。
可以空间优化少一维。先dfs，再递推容易想。题目blog盈利计划