前言
如果觉得太长可以只阅读粗体文字和每部分给出的 最后一个 核心代码块（第一行会注释核心代码）。 偶然的机会让我阅读到了的 dd_engi 算法九讲（由于阿鑫也是看的转载，此处就不提供链接了，大家感兴趣的话直接搜索就可以找到了） 背包问题是比较经典的一种动态规划问题，本文简单介绍了数种背包问题的类型，并给出了相关解决问题的思路，以及给出了相应的例题（每部分例题由易到难，第一题大多为水题）和阿鑫自己写的题解。 才疏学浅，如有纰漏，望指正。
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？——百度百科
01背包
注:最基础，很重要 （万恶之源）
特点:每种物品只有一件
题目形式：有 n 件物品和容量为 c 的背包，第i件物品重量为 w[i],价值为 v[i]，求可以取得的最大价值。
思路：对于每件物品我们只有放入和不放入两种策略。所以对于每个子问题——第 i 件物品是否放入，我们只需要比较，放入第 i 件物品可取得的最大价值 和 不放入第 i 件物品可取得的最大价值，决定是否放入第i件物品。
状态转移方程：
dp[i] [j]=max(dp[i-1] [j],dp[i-1] [j-w[i]]+v[i])
（其中 i 表示只考虑前 i 种物品，j 表示当前容量为 j ，dp[i] [j] 则表示当前情况的最优解，dp[i-1] [j] 代表不放入第 i 件物品的话可以取得的最优解，dp[i-1] [j-w[i]]+v[i]则代表放入第 i 件物品的价值v[i]和剩余背包容量的最大价值dp[i-1] [j-w[i]]之和。
所以该方程的大致意思为： 如果只考虑前 i 种物品时，第 i 种物品是否放入，如果dp[i-1] [j-w[i]]+v[i]更大，则放入更好，如果dp[i-1] [j]更大则代表不放入更好）
//核心代码
for(i=1;i<=n;i++) //只考虑前i件物品
{
for(j=1;j<=c;j++) //当前背包容量为j
{
if(j>=w[i]) //判断是否可以放得下第i件物品
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); //状态转移
else
dp[i][j]=dp[i-1][j]; //状态转移
}
}
可以看出其实dp我们每次只需要考虑上一状态就可以了，所以其实可以优化成如下。
状态转移方程优化：
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
核心代码
//核心代码
for(i=1;i<=n;i++)
{
for(j=c;j>=w[i];j--) //逆序很重要
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]); //状态转移
}
}
注意：里面那层循环的逆序很重要，很重要，很重要。原因如下。
假设有第1件物品重量为1，价值为1,背包容量为3。如果不逆序的话，在第一次循环时会发现
dp[1]=1；
dp[2]=max(dp[2],dp[2-1]+v[1])=2;
dp[3]=max(dp[3],dp[3-1]+v[1])=3。
但我们知道在第一次循环时，只考虑物品1，并且每种物品只能取一次或不取，所以第一次循环后应为dp[1]=dp[2]=dp[3]=1，显然物品1被取得了多次（不合 01背包问题 题意,但符合 完全背包问题 ）。
那为何会有物品被取得多次，而逆序就可以解决这个问题呢？
这首先要回到优化前的状态转移方程： dp[i] [j]=max(dp[i-1] [j],dp[i-1] [j-w[i]]+v[i])
可以看到dp[i] []是和dp[i-1] []有关的，也就是dp的上一个状态。如果我们不逆序：
for(j=w[i];j<=c;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
可以看到 dp[j-w[i]] 可能是之前已经更新过的dp[j]（ j-w[i] 可能在 w[i] 到 j 的范围内），
也就是说 dp[j] 为 dp[j-w[i]]+v[i] 时可能会访问到本次刚更新的dp，相当于可能 dp[i] [j] = dp[i] [j-w[i]]+v[i] 。从而造成了存在物品被放入多次的可能。而逆序就很好的解决了这个问题。
for(j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
可以看到因为 j-- ，j-w[i] 单调递减，j 单调递减, j-w[i] < j < j更 （j更 即本次循环已更新过的下标）恒成立，即避免了dp[j]访问到本次刚更新的dp的问题。
洛谷P1048 [NOIP2005 普及组
例题1：洛谷P1048 [NOIP2005 普及组] 采药 这里只给出状态转移方程优化后的版本。
//用时：37ms(O2优化:34ms) 内存：856.00KB
#include <iostream>
using namespace std;
int w[1005],v[1005],dp[1005];
int main()
{
int i,j,t,m;
scanf("%d%d",&t,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&w[i],&v[i]);
}
//核心代码
for(i=1;i<=m;i++)
{
for(j=t;j>=w[i];j--) //逆序很重要
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]); //状态转移
}
}
printf("%d\n",dp[t]);
return 0;
}
洛谷P3985 不开心的金明
在这里插入代码片
洛谷P4141 消失之物
在这里插入代码片
完全背包问题
特点:每种物品有无限件
题目形式：有 n 种物品和容量为 c 的背包，第 i 种物品每件重量为 w[i],价值为 v[i]，求可以取得的最大价值。
思路：对于每件物品我们的问题是放入几件。所以对于每个子问题——第 i 件物品放入几件，我们只需要比较，可以承受范围内放入不同数量第 i 件物品时可取得的最大价值，来决定放入几件第i件物品。
状态转移方程：
dp[i] [j]=max(dp[i-1] [j],dp[i-1] [j-k w[i]]+ k v[i]) （0<=k * w[i]<= c）
（其中 i 表示只考虑前 i 种物品，j 表示当前容量为 j ，k表示放入k个物品i，dp[i] [j] 则表示当前情况的最优解，dp[i-1] [j] 代表不放入第 i 件物品的话可以取得的最优解，dp[i-1] [j-k w[i]]+ k v[i]则代表放入 k 件第 i 件物品的价值 k v[i] 和剩余背包容量的最大价值 dp[i-1] [j-k w[i]] 之和。
所以该方程的大致意思为： 如果只考虑前 i 种物品时，第 i 种物品放入几件时取得最优解）
于是有了最初的代码 （实际上这段代码对做题没用，一看就会有超时，数组开不出那么大之类的问题，给出是为了方便理解后面的优化）
//核心代码
for(i=1;i<=n;i++) //只考虑前i件物品
{
for(j=1;j<=c;j++) //当前背包容量为j
{
dp[i][j]=dp[i-1][j]; //状态转移
for(k=1;k*w[i]<=j;k++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+ k*v[i]); //状态转移
}
}
}
首先 dp[i] [j]=dp[i-1] [j] 很容易看出其实二维数组中有一维是没用的，于是乎：
for(i=1;i<=n;i++) //只考虑前i件物品
{
for(j=w[i];j<=c;j++) //当前背包容量为j
{
for(k=1;k*w[i]<=j;k++)
{
dp[j]=max(dp[j],dp[j-k*w[i]]+ k*v[i]); //状态转移
}
}
}
这样似乎解决了数组开不了太大的问题，但是题目数据一般都不小欸，三重这样的循环会超时吧（很大概率是会的，阿鑫尝试了下，这样子写本部分的水题都只有80分）。
如何去减少掉里面那层循环呢，其实第一部分01背包问题时已经提及过了。
咳咳，于是乎就有了下面代码。
优化后的核心代码
//核心代码
for(i=1;i<=n;i++)
{
for(j=w[i];j<=c;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]); //状态转移
}
}
为什么呢？原因在前面01背包问题状态转移方程处已经说过了，再粘贴过来也没必要，就换另外一种方式简洁地解释下吧，大家觉得没有例子不好理解的话，可以看前面01背包处的解释。
dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 顺序时判断的是此时是否放入第i件物品，不在乎是否放过第i件物品。
j-w[i]可能大于x*w[i]（x为正整数），dp[j-w[i]]里面可能已经放入了x件物品i。
洛谷P1616 疯狂的采药
//用时：177ms(O2优化:139ms) 内存：80.41MB
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000005
long long dp[MAXN],a[MAXN],b[MAXN];
int main()
{
int t,m;
cin>>t>>m;
int i,j;
for(i=1;i<=m;i++)
cin>>a[i]>>b[i];
//核心代码
for(i=1;i<=m;i++){
for(j=a[i];j<=t;j++){
dp[j]=max(dp[j],dp[j-a[i]]+b[i]); //状态转移
}
}
cout<<dp[t];
return 0;
}
多重背包问题
特点:每种物品有 x[i] 件。（x为正整数）
题目形式：有 n 种物品和容量为 c 的背包，第 i 种物品每件重量为 w[i],价值为 v[i]，有 x[i]件。求可以取得的最大价值。
状态转移方程：
dp[i] [j]=max(dp[i-1] [j],dp[i-1] [j-k w[i]]+ k v[i]) （0<=k<=x[i]）
（其中 i 表示只考虑前 i 种物品，j 表示当前容量为 j ，k表示放入k件物品i，dp[i] [j] 则表示当前情况的最优解，dp[i-1] [j] 代表不放入第 i 件物品的话可以取得的最优解，dp[i-1] [j-k w[i]]+ k v[i]则代表放入 k 件第 i 件物品的价值 k v[i] 和剩余背包容量的最大价值 dp[i-1] [j-k w[i]] 之和。
所以该方程的大致意思为： 如果只考虑前 i 种物品时，第 i 种物品放入几件时取得最优解）
//核心代码
优化后的核心代码
//核心代码
for(i=1;i<=n;i++){
for(j=c;j>=w[i];j--){ //注意逆序，防止重复放入
for(k=1;k<=x[i]&&k*w[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
}
}
}
Acwing4. 多重背包问题 I
#include <bits/stdc++.h>
using namespace std;
int N,V,v[105],w[105],s[105],dp[10005];
int main()
{
cin>>N>>V;
int i,j,k;
for(i=1;i<=N;i++){
scanf("%d%d%d",&v[i],&w[i],&s[i]);
}
for(i=1;i<=N;i++){
for(j=V;j>=v[i];j--){
for(k=1;k<=s[i]&&k*v[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[V]<<endl;
return 0;
}