目录
那年深夏
从晚霞漫天到黑暗阴森，只是一瞬。一阵晚风吹来，传来乌鸦沙哑的嘶鸣，将似暗未暗的荒野衬得更加寂寥了。
夜色降临，惨淡的月光洒满大地，荒寂的草丛在清冷月光的照耀下，生出无数诡秘暗影。小坟，单铲，一人。空灵中，乌鸦落地，一对皮靴，踏着稀草走来，一支手枪在残星中，若隐若现。
急促的喘息，伴着无限的悔恨，在飞快地装着物品。一件件珍物，从亡灵手中夺去，又经过精密的计算，动态规划算法的处理，装进背包。
站起，提包，正去。“乌——”乌鸦嘶叫一声，一颗子弹划破夜空……
引入
上面的东西，目的在于骗取吸引读者，并回应某些人。同时，也起到了引出下文、暗示中心的目的。
没错，从标黑字体可以看出，今天我们要讲的是：背包问题。而且，我们用的是动态规划的算法。
动态规划是什么？
动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
百度的还是那么严谨枯燥，简单来说，动态规划即：
通过将问题拆分成一个一个小问题，记录过往结果，减少重复运算。
举个栗子：
A ： "1+1+1+1+1+1+1+1 =？"
A ： "上面等式的值是多少"
B ： 计算 "8"
A : 在上面等式的左边写上 "1+" 呢？
A : "此时等式的值为多少"
B : 很快得出答案 "9"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"
感谢🙇
2.什么是背包问题？
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。
常见分类：
01背包
完全背包
多重背包
分组背包
今天我们将讲解前两种——01背包和完全背包，以及方案数填满型背包。
3.背包问题的使用价值
背包问题在现实中也有着广泛的应用，很多实际问题都可以被抽象为背包问题，比如股市投资、国家预算、资源分配，工业生产和运输，军事等。
01背包
题目
最基本的背包问题就是01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
用纯暴力思想分析
既然有东西、有重量，那么我们可以选择装或不装，用递归即可实现。
有趣，提到了装或不装这个概念，我们就在这点上找找，看下有什么发现。
动态规划思想来做
二维版
我们的目标是书包内物品的总价值，而变量是物品和书包的限重（表示为w），所以我们可定义状态dp:
dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W
那么我们可以将dp[0][0...总重]初始化为0，表示将前0个物品（即没有物品）装入书包的最大价值为0。那么当 i > 0 时dp[i][j]有两种情况：
1.不装入第i件物品，即dp[i−1][j]；
2.装入第i件物品（前提是能装下），即f[i−1][j−w[i]] + v[i]。
因为情况2有个能装下的前提，因此需要if语句。
因为需要的是最大价值，因此用max()函数取大，则可列出如下代码：
for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(m-w[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]+v[i]); else f[i][j]=f[i-1][j]; } }
一维优化版
经过观察可以发现，f[i][j]需要的只与其上与其左有关，那么我们就可以进行优化.
先把上述冗余的i删掉，然后把if语句提到for循环里（需要一个简单的逻辑，这里就不讲了）
不过，要倒叙来进行操作。因为与其左边也有关联；如果是正序，用到的是f[i][j-w[i]]，而非f[i-1][j-w[i]+v[i]。这就错了。
for(int i=1;i<=n;i++) { for(int j=m;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]+v[i]); } }
变式
读题
【背包练习】金明的预算方案
【题意】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 |
附件 |
电脑 |
打印机，扫描仪 |
书柜 |
图书 |
书桌 |
台灯，文具 |
工作椅 |
无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。
金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
【输入格式】
第1行为两个正整数N、m，N表示总钱数，m为希望购买物品的个数（N<32000，m<60）。
下来m行，每行给出了编号为i的物品的基本数据，每行有3个非负整数v、p、q（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）。
【输出格式】
只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。
【样例输入】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
【样例输出】
2200
分析
很显然，这就是在01背包的基础上，增加了主件与附件。而且附件不超过2件。在输入时将主副件捆绑在一起。
那么，就有5种操作：
1.什么都不取
2.只取主件
3.取主件又取1号附件
4.取主件又取2号附件
5.取主件且取1、2号附件
代码实现
#include<bits/stdc++.h> using namespace std; int n,m,w[66][3],v[66][3],f[56666]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(z==0) { w[i][0]=x; v[i][0]=x*y; } else { if(w[z][1]) { w[z][2]=x; v[z][2]=x*y; } else { w[z][1]=x; v[z][1]=x*y; } } } for(int i=1;i<=n;i++) { if(w[i][0]) { for(int j=m;j>=w[i][0];j--) { f[j]=max(f[j],f[j-w[i][0]]+v[i][0]); if(w[i][1]&&j-w[i][0]>=w[i][1]) { f[j]=max(f[j],f[j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]); } if(w[i][2]&&j-w[i][0]>=w[i][2]) { f[j]=max(f[j],f[j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]); } if(w[i][2]&&j-w[i][0]>=w[i][1]+w[i][2]) { f[j]=max(f[j],f[j-w[i][0]-w[i][2]-w[i][1]]+v[i][0]+v[i][2]+v[i][1]); } } } } printf("%d",f[m]); }
完全背包
题目
小明背着一个背包（最大能带的重量为T）走进一个山洞，山洞里有n种 宝石（每种宝石无限多个），第 i 种 宝石的重量为ti，拿到宝石店能卖mi块钱。
求在背包能承受重量的范围内，使得小明装进背包的宝石总价值最大。
分析
完全背包与01背包不同就是每种物品可以有无限多个。
我们的目标和变量和01背包没有区别，所以我们可定义与01背包问题几乎完全相同的状态dp:
dp[i][j]表示将前i种物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W
那么dp[i][j]也有两种情况：
1.不装入第i种物品，即dp[i][j]=dp[i-2][j]；
2.装入第i种物品，此时和01背包不太一样，因为每种物品有无限个，所以此时不应该转移到dp[i−1][j−w[i]]而应该转变到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品。
同样，我们也可以进行转化，变为一维。只需将01背包第二层循环的倒叙变为正序即可。因为此时计算f[j]时用到了 f[jj] （jj表示现在之前的j），而 f[jj] 已经有了第i颗宝石的影响，所以f[j]的计算用到了包含第i颗宝石影响的小规模状态，f[j]就相当于有多次第i颗宝石影响，相当于第i颗宝石可以取多次。
所以核心代码如下：
for(int i=1;i<=n;i++) { for(int j=t[i];j<=T;j++) { f[j]=max(f[j],f[j-t[i]]+m[i]); } }
方案数填满型背包
方案数填满型背包分为方案数填满型01背包和方案数填满型完全背包
方案数填满型01背包
题目
【题意】
有N (1 <= N <= 250)个数，每个数v_i (1 <= V_i <= 2,000)，现在要分成两组，两组的和尽量接近，同时需要求出得到最接近和的方案数（mod 1,000,000）。
【输入格式】
第一行N，下来N行，每行一个整数Vi。
【输出格式】
第一行：最小差距。
第二行：得到最小差距的方案数（mod 1000 000）
【样例输入】
5
2
1
8
4
16
【样例输出】
1
1
样例输入
分析
题目本身的问题就不多说，重点研究方案数。
设f[i][j]表示组合成j这个数的方案数。
那就用它本身，表示它本来的方案数，加上拿a[i]的方案数。（因为如果第i件物品放入背包，则背包容量还剩j-w[i],所以要取前i-1件物品放入背包剩余容量j-w[i]的方案数f[i-1][j-w[i]]。）
同理，转化为一维也要转化为倒叙，这里就不再罗嗦了。
代码
#include<bits/stdc++.h> using namespace std; int n,a[2005],f[9999990],sum; int main() { scanf("%d",&n); f[0]=1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } for(int i=1;i<=n;i++) { for(int j=sum/2;j>=a[i];j--) { f[j]=(f[j]+f[j-a[i]])%1000000; } } for(int i=sum/2;i>=0;i--) { if(f[i]>0) { printf("%d\n",sum-i*2); printf("%d",f[i]); exit(0); } } }
方案数填满型完全背包
题目
【问题描述】
有一道数学题， a1*x1+a2*x2+……+an*xn=c。
已知c还有 a1、a2…an，求解x1到xn有多少组解？
【输入】
第一行是n和c。
第二行n个数分别是a1到an。 (保证a1~an,x1~xn,c均为正整数)
【输出】
一个整数，代表总解数（用999983模）。
【样例输入】
2 4
1 2
【样例输出】
3
【限制】
30%的数据满足：n<=10,c<=100
100%的数据满足：n<=100,c<=100000
废话不说，上代码。仅仅就改了一下第二层循环的顺序（具体看上面的完全背包->分析）
代码
#include<bits/stdc++.h> using namespace std; int f[110000],a[110],n,c; int main() { f[0]=1; scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { for(int j=a[i];j<=c;j++) { f[j]=(f[j]+f[j-a[i]])%999983; } } printf("%d",f[c]); }
最后
背包问题作为噩梦的开始，不是很考验思维，有比较固定的格式，被就（即）完（蛋）了
动态规划重在自己理解，因为许多东西是难以用言语表达出来的，看了别人的，反而可能会搞混。。。
