目录
最常见的0-1背包问题：
Question:给定n个物品，第i个物品的重量为wgt[i]、价值为val[i]，和一个容量为cap的背包。每个物品只能选择一次，问在限定背包的容量下能放入物品的最大价值。
观察图下所示，由于物品编号i从1开始计数，数组索引从0开始计数，因此物品i对应重量wgt[i]和价值val[i]。
我们可以将0-1背包问题看作一个由n轮决策组成的过程，对于每个物体都有不放入和放入两种决策，因此该问题满足决策树模型。
该问题的目标是求解“在限定背包容量下能放入物品的最大价值”，因此较大概率是一个动态规划的问题。
第一步：思考每轮的决策，定义状态，从而得到dp表
对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号i和剩余背包容量c，记作[i，c]。
状态[i，c]对应的子问题为：前i个物品在剩余容量为c的背包中的最大价值，记为dp[i，c]。
待求解的是dp[n,cap]，因此需要一个尺寸为(n+1) * (cap+1)的二维dp表。
第二步：找出最优子结构，进而推导出状态转移方程
当我们做出物品i的决策后，剩余的是前i-1个物品的决策，可分为以下两种情况。
- 不放入物品i：背包容量不变，状态变化为[i-1，c].
- 放入物品i：背包容量减少wgt[i-1]，价值增加val[i-1]，状态变化为[i-1,c-wgt[i-1]]。
上述分析揭示了本题的最优子结构：最大价值dp[I,c]等于不放入物品i和放入物品i两种方案中价值更大的那一个。由此可以推导出状态转移方程为：
dp[i，c] = max(dp[i-1，c]，dp[i-1，c-wgt[i-1] ] + val[i-1])
需要注意是，当前物品重量wgt[i-1]超过剩余背包容量c，则只能选择不放入背包。
第三步：确定边界条件和状态转移顺序
当无物品时或无背包剩余容量时最大价值为0，即首列dp[i，0]和首列dp[0,c]都等于0.
当前状态[i，c]从上方的状态[i-1,c]和左上方的状态[i-1,c-wgt[i-1]]转移而来，因此通过两层循环正序遍历整个dp表即可。
根据以上的分析，采取三种方法顺序进行实现暴力搜索，记忆化搜索，动态规划解法。
方法一：暴力搜素
搜索代码需要包含的要素：
- 递归参数：状态[i，c]
- 返回值：子问题的解dp[i，c]
- 终止条件：当物品编号越界I = 0 或背包容量为0时，终止递归并返回价值0.
- 剪枝：当前物品重量超出背包剩余容量时，则只能选择不放入背包。
代码示例：
# python 代码示例
def knapsack_dfs(wgt, val, i, c) :
if i == 0 or c == 0 :
return 0
if wgt[i - 1] > c :
return knapsack(wgt, val, i - 1, c)
nohave = knapsack_dfs(wgt, val, i - 1, c)
have = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
return max(nohave, have)// C++代码示例
int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) :
if (i == 0 || c == 0)
{
return 0 ;
}
if (wgt[i - 1] > c)
{
return knapsackDFS(wgt, val, i - 1, c) ;
}
int nohave = knapsackDFS(wgt, val, i - 1, c) ;
int have = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1] ;
return max(nohave, have) ;如图所示：由于每个物品都会产生选或者不选两条搜索分支，因此时间复杂度为O（2^n）。
观察递归树，容易发现其中存在重叠子问题，例如dp[1,10]。而当物品较多，背包容量较大，尤其是相同重量的物品较多时，重叠子问题的数量将会大幅度增多。
方法二：记忆化搜索
为了保证重叠子问题只被计算一次，我们借助记忆列表mem来记录子问题的解，其中menm[i][c]对应dp[i][c]。
时间复杂度取决于子问题数量,也就是O（n*cap）。
实现代码如下：
# python 代码示例
def knapsack_dfs_mem(wgt, val, i, c, mem) :
if i == 0 or c == 0 :
return 0
if mem[i][c] != -1 :
return mem[i][c]
if wgt[i - 1] > c :
return knapsack_dfs_mem(wgt, val, i - 1, c, mem)
noput = knapsack_dfs_mem(wgt, val, i - 1, c, mem)
yesput = knapsack_dfs_mem(wgt, val, i - 1, c - wgt[i - 1], mem) + val[i - 1]
mem[i][c] = max(noput, yesput)
return mem[i][c]// c++ 代码示例
int knapSackDFSMem(vector<int> &wgt, vector<int> &val, int i, int c, vector<int> &mem)
{
if (i == 0 || c == 0)
{
return 0 ;
}
if (mem[i][c] != 0)
{
return mem[i][c] ;
}
if (wgt[i - 1] > c)
{
return knapSackDFSMem(wgt, val, i - 1, c, mem) ;
}
int noput = knapSackDFSMem(wgt, val, i - 1, c, mem) ;
int yesput = knapSackDFSMem(wgt, val, i - 1, c - wgt[i - 1], mem) + val[i - 1];
mem[i][c] = max(noput, yesput) ;
return mem[i][c] ;
}
方法三：动态规划
动态规划实质是就是在状态转移的过程中填充dp表的过程，
代码如下所示：
# python 代码示例
def knapsack_dp(wgt, val, cap) :
n = len(wgt)
dp = [ [0] * (cap + 1) for _ in range(n + 1)]
for i in range(1, n + 1) :
for c in range(1, cap + 1) :
if wgt[i - 1] > c :
dp[i][c] = dp[i - 1][c]
else :
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
return dp[n][cap] // c++ 代码示例
int knapSackDP(vector<int> &wgt, vector<int> &val, int cap)
{
int n = wgt.size() ;
vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0)) ;
for (int i = 1 ; i <= n ; i++)
{
for (int c = 1 ; c <= cap ; c++)
{
if (wgt[i - 1] > c)
{
dp[i][c] = dp[i - 1][c] ;
}
else
{
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]) ;
}
}
}
return dp[n][cap] ;
}时间复杂度和空间复杂度都是由数组dp所决定的，即O（n*cap）。
如图所示：
方法四：空间优化
由于每个状态都至于其上一行有关系，因此我们可以使用两个数组进行滚动前进，将复杂度从O（n^2）降低为O（n）。
进一步思考，我们能否仅用一个数组实现空间优化？观察可知，每个状态都是有正上方或左上方的格子的状态转移而来。假设只有一个数组，当开始遍历第i行时，该数组存储仍然是第i-1行的状态。
- 如果采取正序遍历，那么遍历到dp[i,j]时，左上方的dp[i-1,1]~dp[i-1,j-1]值可能已经覆盖了，因此无法得到状态转移的正确结果。
- 如果采取倒序遍历，则不会发生覆盖问题，状态转移可以正确的进行。
代码示例：
def knap_sack_dp_comp(wgt, val, cap) :
n = len(wgt)
dp = [0] * (cap + 1)
for i in range(1, n + 1) :
for c in range(cap, 0 ,-1) :
if wgt[i - 1] > c :
dp[c] = dp[c]
else :
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap] // c++ 代码示例
int kanpSackDPComp(vector<int> &wgt, vector<int> &val, int cap)
{
int n = wgt.size() ;
vector<int> dp(cap + 1, 0) ;
for (int i = 1 ; i <= n ; i++)
{
for (int c = cap; c > 0 ; c--)
{
if (wgt[i - 1] > c)
{
dp[c] = dp[c] ;
}
else
{
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) ;
}
}
}
return dp[cap] ;
}