背包
快熄灯了，写得有点急
01背包
给m个物品让你装进最大载重为t的背包，每个物品重量和价值，每种物品只能放一次，问最大价值
朴素做法
设dp[i][j]为只取前i个物品中并且容量为j的最佳情况
可以想到两种情况1.不选当前物体,则dp[i][j]=dp[i-1][j]
2.选当前物体则需要为当前物体腾出来wi的位置，方程为dp[i][j]=dp[i-1][j-w[i]]+v[i].
for(int i=1;i<=m;i++)
{
for(int j=0;j<=t;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
printf("%d",dp[m][t]);
}
优化做法
由于我们每次选择时只涉及到i和i-1，我们可以将二维压缩至一维，至于怎么体现原来的i和i-1，就需要我们在内层循环反着枚举一遍容量。原理是如果我们如果正着枚举那么在我们肯定会先更新dp[j-w[i]]再更新dp[j]，也就是说在更新dpj时必然会收到本次i循环前面的结果的影响，但如果反过来枚举的话就不会收到本次i循环影响，也就是说使用的dp[j-w[i]]都是在i为i-1时的结果，也就是在i-1的基础上更新。
for(int i=1;i<=m;i++)
{
for(int j=t;j>=w[i];j--)
{
dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
}
}
完全背包
和01背包的不同是每个物品可以放多次
最朴素做法是加一层循环看放入多少个i物品
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k*w[i]<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+v[i]*k);
}
}
}
这个是二维优化版本
把所有k拆开我们可以得到dp方程大概是这么个结果，然后我们发现后面的一大坨就等于f[i,j-w[i]]+vi
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=w[i]) dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}
代码和01背包的唯一不同是dp[i][j-w[i]]中在01背包是dp[i-1][j-w[i]].
原因在于01背包只能由上一个物品转移来，而完全背包可以从当前物品转移多次而来.
优化版本
和01背包唯一不同是内层循环是正着枚举
刚才说过如果正着循环会导致当前i影响到结果，但在完全背包中我们一个i需要取多次所以正好需要结果根据当前i进行变动
for(int i=1;i<=n;i++)
{
for(int j=w[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
多重背包
每个物品不是只能取一次也不是无限次而是指定次数，并且每个物品的次数可以不同。
朴素版本
和完全背包最朴素版本基本类似，不过增加一个数量限制不能超过si
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=s[i]&&k*w[i]<=j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]*k]+v[i]*k);
}
}
优化版本
二进制优化法，因为我们种物品都有多个，我们可以将同种物品分为好多堆，采用二进制分法。假如a物品有7个那么就分为1+2+4，如果是8就是1+2+4+1,是15就是1+2+4+8，以此类推。然后我们就将n个a种物品分成了logn个，然后将所有物品都这样分一起做01背包即可。（n以内的每个数都可以被不同堆之间相加所得并且不重复）
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int sum=1;
while(sum<=c)
{
cnt++;
v[cnt]=sum*b;
w[cnt]=sum*a;
c-=sum;
sum*=2;
}
if(c>0)
{
cnt++;
v[cnt]=c*b;
w[cnt]=c*a;
}
}
for(int i=1;i<=cnt;i++)
{
for(int j=m;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
分组背包问题
将物品分为多个组，相同组的物品只能取一次，我们采用三重循环，第二层是由大到小枚举，原因是同组物品只能取一次因此要像01背包一样，大概像是对每一组分别进行01背包的感觉。并且由于每一组内的物品质量不一定相同所以要枚举到0并且要判断当前j是否大于等于物品重量
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)//同组不能重复取
{
for(int k=1;k<=s[i];k++)
{
if(j>=w[i][k]) dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
}
}
}