简单来说就是给一个有一定体积的背包，然后给出一些占体积的物品，需要我们使用dp的方法在相关条件下将物品塞入背包，并达到某些目的（比如物品有价值，得出一定体积背包能得到的最大价值）。
需要的基础：
少量的数学基础（小学水平及以上基本能理解（大概））
对dp思想的一定了解（通过利用已有的子问题信息高效求出当前问题的最优解）
为方便食用，代码无头文件
下面从01背包讲起：
介绍：该类问题每个物品只有两个可能的状态（取和不取）如二进制一般，所以称为01背包问题。
由一道例题引入：
采药
由于样例给的不太好讲解就自己造了一组：
10 4
3 1
1 2
2 4
3 3
就照着这组数据讲吧：
灵魂图示：（其中花盆（矩形）里的数代表着物品的体积，上面的花（圆圈）里的数代表着价值）
不需要先着眼于自己的包多大（因为dp的思想），而是先要考察这些草药能够让某容量的背包装下最大价值的物品（子问题）
只要解决了上述子问题，那么所求问题也解决了~
接下来你开始采药
走到了第一个草药面前
你有将它装入或者不装入背包两种选择
如下表：（第一行代表t容量的背包 第一列代表前i个物品（要注意是前i个不是第i个！））
可知在背包容量大于等于3的时候都可以将①装入，且装入这个选择能取得最大价值（目前）
所以下面我们来更新数据
0123456789100 1 111111112 3 4
类似地，继续向前走，走到②，进一步更新
如何更新呢，比如说，背包容量小于3（>0）时，只能将②放入，且这样做得到价值是最大的，因此1-3全部加上相应价值2
0123456789100 1 111111112 22 3 4接下来考察3-10的格子怎么填，注意，所填的格子的状态受到上一行的影响 例如 对于容量为3的背包，如果你考虑上一行的情况 会发现此时背包已经被装满了，那么此时的价值仍然为1。但是，还不可以将1填入格子中，因为你还没有考虑不选择①的情况，此时如果只选择②，你得到的价值为2 这才是最大价值，进行更新。
而对于容量为4的背包 ①②都可以装，更新为3 容量>3的格子也是3（全部拿完）
下面的格子自己模拟一下吧，在经过一定的模拟后，你会发现这一点：
对于一个格子的最大价值，有且仅有可能从上一行（即历史的状态）转移而来。
现在给出关键的dp方程：（开二维数组是朴素的想法，因为是直接由上面的表得到的）
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);当然，上面的方程是不完整的，当j<c[i]的时候会越界，所以要加上if-else语句（也请理解一下这样的方程的实际意义）
if(j>=c[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]); else dp[i][j]=dp[i-1][j];下面是code：
int c[101];//物品体积 int w[101];//物品价值 int dp[101][10001]; int t,n;//t表示背包容量，n表示物品数量 int main(){ cin>>t>>n; for(int i=1;i<=n;i++) cin>>c[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=t;j>=1;j--){ if(j>=c[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]); else dp[i][j]=dp[i-1][j]; } } cout<<dp[n][t];//已经更新完毕，得到答案 return 0; }
但是，二维数组是很浪费空间的，注意到状态仅由上一行转移而来，我们想到了一维数组的解法：
这里直接给出关键的方程，请读者认真思考一下这样做的合理性：
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);代码：
int c[101];//物品体积 int w[101];//物品价值 int dp[10001]; int t,n;//t表示背包容量，n表示物品数量 int main(){ cin>>t>>n; for(int i=1;i<=n;i++) cin>>c[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=t;j>=c[i];j--){ dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } } cout<<dp[t]; return 0; }注意！在下面的第二个for中，j应该从t开始倒着扫（和模拟的顺序相反），不然会出现一个物品多次放入的情况！（可以自己打表试试）
（注： 事实上，顺着扫正是下面要讲的完全背包的解法。）
这是倒着扫↓
for(int i=1;i<=n;i++){ for(int j=t;j>=c[i];j--){ dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } }而对于二维的做法则没有倒着扫的必要：
在这里，j从t->1或者从1->t都是合法的，因为都是从上一行转移而来，顺序不影响结果。
for(int i=1;i<=n;i++){ for(int j=t;j>=1;j--)//for(int j=1;j<=t;j++)亦可 { if(j>=c[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]); else dp[i][j]=dp[i-1][j]; } }讲完了01背包
下面来讲完全背包
完全背包介绍：
完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次（OI wiki）
例题刚好是采药的变式：
疯狂的采药
我们是否仍然能够使用刚才的情境理解呢？可以：
现在你走到第①棵草药面前，开始疯狂地采（采完之后你就不回头了，这样和上面的01背包一样）
那么在你疯狂地采的过程中，你的各种容量的背包会发生什么样的变化呢，依然用表来理解：
0123456789100 1 111222332 3 4你会发现，你的包容积在 3-5 的时候 仍然只能采摘1个 但在6-8时候可以摘2个 以此类推直到考察到t=10的情况
因此，我们可以使用刚才提及的解法
for(int i=1;i<=n;i++){ for(int j=c[i];j<=t;j++){ dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } }code:
这题范围需要注意 不开long long见祖宗（亲测）
typedef unsigned long long ll; ll c[10000+5];//物品体积 ll w[10000+5];//物品价值 ll dp[10000000+5]; ll t,n;//t表示背包容量，n表示物品数量 int main(){ cin>>t>>n; for(int i=1;i<=n;i++) cin>>c[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=c[i];j<=t;j++){ dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } } cout<<dp[t]; return 0; }
多重背包介绍：
多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品 y 有 k个，而非1个(OI wiki)
我们仍然能够使用开头的情境理解：
走到一棵（一丛）草药前 比如①
就是你可以选一棵草药 那么就和01背包更新方式一样
也可以选两棵 把她们打包成一棵草药（当然价值和体积翻倍）此时，比如开头的第①丛草药对你而言就是一棵 体积3*2 价值1*2的草药，转化成01背包问题进行更新。
类似的，你可以选1-k棵！
理解之后，直接上代码：
int c[101];//物品体积 int w[101];//物品价值 int s[101];//每种物品的数量 int dp[10001]; int t,n;//t表示背包容量，n表示物品种数 int main(){ cin>>t>>n; for(int i=1;i<=n;i++) cin>>c[i]>>w[i]>>s[i]; for(int i=1;i<=n;i++) for(int k=1;k<=s[i];k++) for(int j=t;j>=k*c[i];j--) dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]); cout<<dp[t]; return 0; }
（更新中）
