首先安利一发背包九讲：https://www.cnblogs.com/jbelial/articles/2116074.html

简单说说今天学到的

一：01背包问题 （每个物体只能拿一次，要求在一定的空间内，拿物体使得到的价值最大）

有两种写法，一种是二维数组，一种是一维数组（省空间）

1.二维dp的模板：（很奇怪这种方式在有多个样例输入的情况下，不用清空dp数组）

状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);

基本操作：

if(j>=wei[i]) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);//i为面对第几个物体了 //j为所占的空间大小下，dp数组存的是对应的价值 } else//这种写二维的方式可不清空 { dp[i][j]=dp[i-1][j]; } 2.一维dp的模板（这种方式切记清空dp数组，还有就是注意要从后往前逆序推，因为这样得到的才是上一个状态的，否则会重复计算）

模板：

状态转移方程：dp[j]=max(dp[j],dp[j-wei[i]]+val[i]);

基本操作：

memset(dp,0,sizeof(dp));//一维记得清空 for(int i=1;i<=n;++i) { for(int j=v;j>=wei[i];--j) { dp[j]=max(dp[j],dp[j-wei[i]]+val[i]); } } cout<<dp[v]<<endl; 总结：简单来说就是对于每一个物体有两种选择，要么拿要么不拿，如不拿就继承上一个状态，否则就上一个状态的dp的值加上当前物体的价值。

二：完全背包问题 （每个物体可以拿无数次，要求在一定的空间内，拿物体使得到的价值最大）

板子：

状态转移方程：dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

基本操作：

for(i=1;i<=n;i++) for(j=w[i];j<=m;j++) //注意此处与01背包不同，01为倒序

dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

优化：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。

三、多重背包问题 （每个物体最多可以拿c【i】次，即次数限制可能不同。要求在一定的空间内，拿物体使得到的价值最大）

板子：（该板子参考：https://blog.csdn.net/qq_41117236/article/details/80986564）

状态转移方程：dp[j]=MAX{dp[j],dp[j-kw[i]]+kv[i]};

基本操作：

for(i=1;i<=n;i++) for(j=m;j>=0;j--) for(k=0;k<=c[i];k++) { if(j-kw[i]<0) break; dp[j]=max(dp[j],dp[j-kw[i]]+k*v[i]); }

ps：提一下刚好满背包的容量要求下求max/min价值的题： 例子：http://acm.hdu.edu.cn/showproblem.php?pid=1114

要求对于给定总重量的硬币，所能得到的最少金额。如果无法恰好得到给定的重量，输出-1

代码：

#include <bits/stdc++.h> #define ll long long #define N 10005 using namespace std; const int modd=1e9+7; ll inf=0x3f3f3f3f; ll dp[N],val[N],wei[N];//重量、个数 ，求min int main() { int t,k; cin>>t; while(t--) { int emptw,fullw; cin>>emptw>>fullw; fullw=fullw-emptw; //memset(dp,0,sizeof(dp)); //这种二维dp方式需要清空 int n; cin>>n; for(int i=1;i<=n;++i) cin>>val[i]>>wei[i]; for(int i=0;i<N;++i) { if(i==0) dp[i]=0; else dp[i]=inf;

}
	for(int i=1;i<=n;++i)//一定重量拿min钱 
	{
		for(int j=fullw;j>=wei[i];--j)
		{
			for(int k=1;k*wei[i]<=j;++k)
			{
				dp[j]=min(dp[j],dp[j-k*wei[i]]+k*val[i]);
			
			}
		}
	} 
	if(dp[fullw]!=inf)
		cout<<"The minimum amount of money in the piggy-bank is "<<dp[fullw]<<"."<<endl; 
	else
		cout<<"This is impossible."<<endl;
 }
return 0;

} 总结：完全背包装满问题中：求最大最小值可以从初始化入手

如果是要求背包装满的前提下，求最小值，dp[0]=0，dp[ ]的其他置为inf即可 如果是要求求最大值，dp[0]=0，dp[ ]的其他置为-inf即可

#long long inf =0x3f3f3f3f//无穷大 ———————————————— 版权声明：本文为CSDN博主「suheyin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/suheyin/article/details/86485399