专栏首页Urlteam背包九讲之多重背包&&混合背包详解

背包九讲之多重背包&&混合背包详解

多重背包,算是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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • git–在树莓派(新电脑)重新用git进行pull以及push

    期待已久的树莓派今天刚刚收到,则也在树莓派上面搭建git。同时这个过程略艰辛故记录之。

    十四君
  • acm比赛刷题小技巧

    2.有时候int型不够用,可以用long long或__int64型(两个下划线__)。

    十四君
  • 背包九讲之分组背包-HDU1712题解

    以杭电1712为例子http://acm.hdu.edu.cn/showproblem.php?pid=1712

    十四君
  • hdu 2473 Junk-Mail Filter (并查集之点的删除)

    Junk-Mail Filter Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/...

    Gxjun
  • Codeforces 626F Group Projects(滚动数组+差分dp)

    F. Group Projects time limit per test:2 seconds memory limit per test:256 megaby...

    Angel_Kitty
  • hdu----(1528)Card Game Cheater(最大匹配/贪心)

    Card Game Cheater Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

    Gxjun
  • HDU 5536--Chip Factory(暴力)

    Chip Factory Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/26...

    Enterprise_
  • Code Forces 645A Amity Assessment

    A. Amity Assessment time limit per test2 seconds memory limit per test256 me...

    ShenduCC
  • Codeforces 626E Simple Skewness(暴力枚举+二分)

    E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

    Angel_Kitty
  • 【Codeforces】1213B - Bad Prices

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券