背包九讲之多重背包&&混合背包详解
多重背包，算是01和完全的结合体，这次运用上模板解题。
1：题目描述
http://acm.nyist.net/JudgeOnline/problem.php?pid=546
Divideing Jewels
时间限制：1000 ms | 内存限制：65535 KB
难度：4
描述
Mary and Rose own a collection of jewells. They want to split the collection among themselves so that both receive an equal share of the jewels. This would be easy if all the jewels had the same value, because then they could just split the collection in half. But unfortunately, some of the jewels are larger, or more beautiful than others. So, Mary and Rose start by assigning a value, a natural number between one and ten, to each jewel. Now they want to divide the jewels so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the jewels in this way (even if the total value of all jewels is even). For example, if there are one jewel of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the jewels.
输入
Each line in the input file describes one collection of jewels to be divided. The lines contain ten non-negative integers n1 , . . . , n10 , where ni is the number of jewels of value i. The maximum total number of jewells will be 10000. The last line of the input file will be “0 0 0 0 0 0 0 0 0 0”; do not process this line. 输出
For each collection, output “#k:”, where k is the number of the test case, and then either “Can be divided.” or “Can’t be divided.”. Output a blank line after each test case. 样例输入
1 0 1 2 0 0 0 0 2 0
1 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0样例输出
#1:Can’t be divided.
#2:Can be divided.
大致的意思是：
就是先计算出总的珠宝的价值，看其是否为偶数，不是偶数肯定不能平分，
若为偶数，视为多重背包问题即可！~
2：解题模板代码：
# include<stdio.h>
# include<string.h>
int w[15],n[15],f[500000],V;
void ZeroOnePack(int cost,int weight)//01背包
{
int v;
for(v=V;v>=cost;v--)
if(f[v]<f[v-cost]+weight)
f[v]=f[v-cost]+weight;
}
void CompletePack(int cost,int weight)//完全背包
{
int v;
for(v=cost;v<=V;v++)
if(f[v]<f[v-cost]+weight)
f[v]=f[v-cost]+weight;
}
void MultiplePack(int cost,int weight,int amount)//多重背包
{
int k;
if (cost*amount>=V)
{
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 i,j,t=1,a[10],sum;
while(scanf("%d%d%d%d%d%d%d%d%d%d",&a[1],&a[2],&a[3],
&a[4],&a[5],&a[6],&a[7],&a[8],&a[9],&a[10]))
{
if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0
&&a[6]==0&&a[7]==0&&a[8]==0&&a[9]==0&&a[10]==0)
break;//结束条件
sum=0;j=1;
for(i=1;i<=10;i++)
{
sum+=a[i]*i;
if(a[i])
{
w[j]=i;
n[j]=a[i];
j++;
}
}
printf("#%d:",t);
if(sum%2==1)
printf("Can't be divided.\n");
else
{
V=sum/2;
memset(f,0,sizeof(f));
for(i=1;i<j;i++)
MultiplePack(w[i],w[i],n[i]);
if(f[V]==V)
printf("Can be divided.\n");
else
printf("Can't be divided.\n");
}
printf("\n");
t++;
}
return 0;
}
3：关键方法解析：
本质上，多重背包就是当成01背包来解决的。，即使有多个物品，则相等于多出多个01背包的物品而已，但是为了做时间上的优化，则采用分割物品的方法。
如果他的物品数量可以等同与完全背包则调用完全背包的解法。否则是调用01背包的解法。
void MultiplePack(int cost,int weight,int amount)//多重背包
{
int k;
if (cost*amount>=V)
{
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);
}好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。
这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为O(V*Σlog n[i])的01背包问题，是很大的改进。
4：混合背包
调用我们前面给出的三个相关过程。
for i=1..N
if 第i件物品是01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品是完全背包
CompletePack(c[i],w[i])
else if 第i件物品是多重背包
MultiplePack(c[i],w[i],n[i])
原创文章，转载请注明： 转载自URl-team
本文链接地址: 背包九讲之多重背包&&混合背包详解
No related posts.