问题: 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是c[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
思路： 这和01背包的区别不就是可以多选很多次吗，把它拆成01背包不就得了。
状态转移方程： f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i] (0<=k*w[i]<= v)
降维：
首先看伪代码：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-w[i]]+c[i]};
为什么是正着循环嘞？
首先想想为什么01背包问题中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-w[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-w[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-w[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。
这个算法也可以以另外的思路得出。
例如，基本思路中的状态转移方程可以等价地变形成这种形式：f[i][v]=max{f[i-1][v],f[i][v-w[i]]+c[i]}，将这个方程用一维数组实现，便得到了上面的伪代码。
庆功会
【问题描述】为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入格式】第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=10。
【输出格式】第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
【输入样例】 【输出样例】
5 1000 1040
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
法一 朴素算法
//多重背包 朴素算法 #include#include #include #include using namespace std;int n,m;//n奖品数，m拨款数int v[6505],w[6505],s[6501];//价格，价值，最大数量 int f[6002];int main(){ scanf("%d%d",&n,&m) ; for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&s[i]); for(int i=1;i<=n;i++)//选到第i个物品 for(int j=m;j>=0;j--)//剩余的钱数 for(int k=0;k<=s[i];k++)//看选几个最大 { if(j-k*v[i]<0) break;//剩余的钱不够买k件物品 f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);//比较买几件最大 } printf("%d",f[m]); return 0;}
法二 进行二进制优化转换成01背包
#include#include #include #include using namespace std;int n,m,nl;//n奖品数，m拨款数int v[10001],w[10001];//价格，价值，最大数量int f[6002];int main(){ scanf("%d%d",&n,&m) ; for(int i=1;i<=n;i++) { int x,y,s,t=1; scanf("%d%d%d",&x,&y,&s); while(s>=t) { v[++nl]=x*t; w[nl]=y*t; s-=t; t*=2; } v[++nl]=x*s; w[nl]=y*s; }for(int i=1;i<=nl;i++) for(int j=m;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); printf("%d",f[m]);return 0; }