[文章目录]
Description
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
PO姐给的建议，拆包时可以不用真正的拆，用一个变量存一下1、2、4、8......就行了。（别忘了剩余也要拆）。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int v,t;
int f[210];
int main()
{
scanf("%d%d",&v,&t);
for(int x,y,z,i=1;i<=t;i++)
{
scanf("%d%d%d",&x,&y,&z);
int tmp=1;
if(!z)
{
for(int j=x;j<=v;j++)
{
f[j]=max(f[j],f[j-x]+y);
}
continue;
}
while(z>=tmp)
{
for(int j=v;j>=x*tmp;j--)
{
f[j]=max(f[j],f[j-x*tmp]+y*tmp);
}
z-=tmp;
tmp*=2;
}
if(z)
for(int j=v;j>=z*x;j--)
{
f[j]=max(f[j],f[j-x*z]+y*z);
}
}
printf("%d",f[v]);
return 0;
}