#include <bits/stdc++.h>
using namespace std;
#define N 107
int dp[N];
int v[N]; // 体积
int w[N]; // 价值
int n, tar;
void ZeroOnePack(int V, int W) {
for (int v=tar; v>=V; v--)
dp[v] = max(dp[v-V] + W, dp[v]);
}
int main() {
freopen("in.txt", "r", stdin);
cin >> n >> tar;
for (int i=1; i<=n; i++) cin >> w[i] >> v[i];
for (int i=1; i<=n; i++) {
ZeroOnePack(v[i], w[i]);
}
cout << dp[tar] << endl;
}
恰好装满背包，那末就是除dp[0]是0以外，其他的都是-INF
如果是不能装满背包，那末dp所有的值，都是0
下面相同
void CompletePack(int V, int W) {
for (int v=V; v<=tar; v++) {
dp[v] = max(dp[v-V]+W, dp[v]);
}
}
这是1个多重背包的模板，也是10分好用的1种模板，由于这个比直接撤除01 背包来做要省些时间。这是为啥呢，首先先由我讲1下为何能换成01 背包吧。
举个栗子吧。 假设给了我们 价值为 2，但是数量却是10 的物品，我们应当把10给拆开，要知道2进制可是能够表示任何数的，所以10 就是可以有1，2, 4，8以内的数把它组成，1开始我们选上 1了，然后让10⑴=9，再选上2,9⑵=7，在选上 4,7⑷=3，
而这时候的3<8了，所以我们就是可以得出 10由 1,2,4,3，来组成，就是这个数量为1,2,3,4的物品了，那末他们的价值是甚么呢，是2,4,6,8，也就说给我们的价值为2，数量是10的这批货物，已转化成了价值分别是2,4,6,8元的货物了，每种只有1件哎！！！！这就是2进制优化的思想。
那为何会有完全背包和01 背包的不同使用加判断呢？缘由也很简单啊，当数据很大，大于背包的容纳量时，我们就是在这个物品中取上几件就是了，获得量时不知道的，也就理解为无穷的啦，这就是完全背包啦，反而小于容纳量的就是转化为01背包来处理就是了，可以大量的省时间。
#include<string.h>
#include<stdlib.h>
#define N 1000 //物品个数
#define M 100000000 //所有物品可能的最大价值
int m[N],c[N],w[N],f[M];
int V;
int max(int a,int b){return a>b?a:b;}
void ZeroOnePack(int cost,int weight)
{
int v;
for(v=V;v>=cost;v--) f[v]=max(f[v],f[v-cost]+weight);
}
void CompletePack(int cost,int weight)
{
int v;
for(v=cost;v<=V;v++)
f[v]=max(f[v],f[v-cost]+weight);
}
void MultiplePack(int cost,int weight,int amount)
{
int k;
if(cost*amount>=V) // 实际上这里转化成了1个无穷数量的完全背包。
{
CompletePack(cost,weight);
return;
}
k=1;
while(k<amount)
{
ZeroOnePack(k*cost,k*weight);
amount=amount-k;
k=k*2;
}
ZeroOnePack(amount*cost,amount*weight);
}
int main()
{
int n,i;
scanf("%d %d",&n,&V);
// 两种不同的初始化方式，根据情况自行选择
//memset(f,0,sizeof(f[0])*(V+1)); // 只希望价格尽可能大
//memset(f,-M,sizeof(f[0])*(V+1));f[0]=0; // 要求恰好装满背包
for(i=0;i<n;i++) scanf("%d %d %d",m+i,c+i,w+i);
for(i=0;i<n;i++) MultiplePack(c[i],w[i],m[i]);
printf("%d\n",f[V]);
system("PAUSE");
return 0;
}
本质是保护1个滑动的窗口，窗口的大小不能超过 m[i]的大小
因而根据w[i]的大小，将原来的j划分成了w[i]个等价类，每一个等价类，可以进行单调队列的保护。
将每一个等价类保护1遍以后，就是完成了i个物品的工作
实际上我们可以模仿，01背包问题，进行数组的重复利用
先看1个例子：取m[i] = 2, v[i] = v, w[i] = w, V > 9 * v，
并假定 f(j) = F[i - 1][j]，视察公式右侧要求最大值的几项：
j = 6*v: f(6*v)、f(5*v)+w、f(4*v)+2*w 这3个中的最大值
j = 5*v: f(5*v)、f(4*v)+w、f(3*v)+2*w 这3个中的最大值
j = 4*v: f(4*v)、f(3*v)+w、f(2*v)+2*w 这3个中的最大值
明显，公式㈠右侧求最大值的几项随j值改变而改变，但如果将j = 6*v时，每项减去6*w，j=5*v时，每项减去5*w，j=4*v时，每项减去4*w，就得到：
j = 6*v: f(6*v)-6*w、f(5*v)-5*w、f(4*v)-4*w 这3个中的最大值
j = 5*v: f(5*v)-5*w、f(4*v)-4*w、f(3*v)-3*w 这3个中的最大值
j = 4*v: f(4*v)-4*w、f(3*v)-3*w、f(2*v)-2*w 这3个中的最大值因此队列中我们是保护1个单调的函数，但是真正使用的时候，我们对这个函数进行适当的处理便可。
#include <iostream>
using namespace std;
#define N 107
int n, tar;
int v[N], w[N], m[N];
int dp[N]; // 转动数组
int deq[N]; // 单调队列，下标
int deqv[N]; // 单调队列，值
void solve() {
for (int i=0; i<n; i++) { // 枚举每一个物品
for (int a=0; a<v[i]; a++) { // 1共v[i]个等价类
int s =0, t = 0; //双端队列的头部和尾部
for (int j=0; j*v[i] + a<=tar; j++) { // 每一个等价类中符合条件的j有哪些
// 加入j构成的函数的时候，保证队列的单调性
int val = dp[j * v[i] + a] - j * w[i];
while (s < t && deqv[t -1] <= val) t--;
deq[t] = j;
deqv[t] = val;
t ++;
// 从头部取出，t
dp[j*v[i] + a] = deqv[s] + j * w[i];
//判断队列的长度是否是太长了
if (deq[s] == j-m[i]) {
s ++;
}
}
}
}
cout << dp[tar] << endl;
}
for i = 1 to N
if 第i件物品属于01背包
ZeroOnePack(F,Ci,Wi)
else if 第i件物品属于完全背包
CompletePack(F,Ci,Wi)
else if 第i件物品属于多重背包
MultiplePack(F,Ci,Wi,Ni)5.1 问题
2维费用的背包问题是指：对每件物品，具有两种不同的空间耗费，选
择这件物品必须同时付出这两种代价。对每种代价都有1个可付出的最大值
（背包容量）。问怎样选择物品可以得到最大的价值。
设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别
为Ci和Di。两种代价可付出的最大值（两种背包容量）分别为V 和U。物品的
价值为Wi。
5.2 算法
费用加了1维，只需状态也加1维便可。设F [i,v,u]表示前i件物品付出两
种代价分别为v和u时可取得的最大价值。状态转移方程就是：
F [i,v,u] = max{F[i − 1, v, u], F[i − 1, v − Ci, u − Di] + Wi}
如前述优化空间复杂度的方法，可以只使用2维的数组：当每件物品只可
以取1次时变量v和u采取逆序的循环，当物品有如完全背包问题时采取顺序的
循环，当物品有如多重背包问题时拆分物品。
这里就不再给出伪代码了，相信有了前面的基础，读者应当能够自己实现
出这个问题的程序。有时，“2维费用”的条件是以这样1种隐含的方式给出的：最多只能
取U件物品。这事实上相当于每件物品多了1种“件数”的费用，每一个物品的
件数费用均为1，可以付出的最大件数费用为U。换句话说，设F [v,u]表示付
出费用v、最多选u件时可得到的最大价值，则根据物品的类型（01、完全、多
重）用不同的方法循环更新，最后在f[0...V, 0...U]范围内寻觅答案。
有N件物品和1个容量为V 的背包。第i件物品的费用是Ci，价值是Wi。这
些物品被划分为K组，每组中的物品相互冲突，最多选1件。求解将哪些物品
装入背包可以使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
这个问题变成了每组物品有若干种策略：是选择本组的某1件，还是1件
都不选。也就是说设F [k, v]表示前k组物品花费费用v能获得的最大权值，则
有：
F [k, v] = max{F [k − 1, v], F [k − 1, v − Ci] + Wi | item i ∈ group k}
使用1维数组的伪代码以下：
for k = 1 to K
for v = V to 0
for item i in group k
F [v] = max{F [v], F [v − Ci] + Wi}
这里3层循环的顺序保证了每组内的物品最多只有1个会被添加到背包中。
另外，明显可以对每组内的物品利用2.3中的优化。
小结
分组的背包问题将彼此互斥的若干物品称为1个组，这建立了1个很好的
模型。很多背包问题的变形都可以转化为分组的背包问题（例如7），由分组的
背包问题进1步可定义“泛化物品”的概念，10分有益于解题。
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
