NOI题库--砝码称重V2(多重背包2^n拆分)

时间:2022-02-23 14:28:45
以前只会写多重背包的原版,渣的不行,为了做此题不得不学习了一下,发现其实也不难,只要理解了方法就好多了(PS:其实和倍增挺像的)

8756:砝码称重V2

总时间限制: 1000ms 内存限制: 65536kB

描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=100,000),要求:计算用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况。

输入

一行,包括六个正整数a1,a2,a3,a4,a5,a6,表示1g砝码有a1个,2g砝码有a2个,……,20g砝码有a6个。相邻两个整数之间用单个空格隔开。

输出

以“Total=N”的形式输出,其中N为可以称出的不同重量的个数。

样例输入

1 1 0 0 0 0

样例输出

Total=3

提示

样例给出的砝码可以称出1g,2g,3g三种不同的重量。

多重背包的2^n拆分,就是把一种多份的物体分解成几种价值高的物体来进行01背包就好,举个栗子:

**对于数量为 n 的同种物品 k 价值为 v

可以拆分打包为 1 , 2 , 4 , 8 , 16 …… ,2^x , n的剩余数量

价值为 v , 2*v ……

例如 32 个 价值为 2 的物品可以拆为

1个价值为 1*2 的物品,

1个价值为 2*2 的物品,

1个价值为 4*2 的物品,

1个价值为 8*2 的物品,

1个价值为 16*2 的物品,

1个价值为 31*2 的物品,

用这6个物品可以组合出原先32个物品的所有状态**

下面是代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000100]={0};
int f[1000100]={0};
int zz=0;
int value[7]={0,1,2,3,5,10,20};
int fm[7]={0};
int sum=0;
int total=0;
const int cf[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
//以二为底的指数为i的值
void fj(int ki,int valuei)//二进制分解的过程
{
int i=0;
while (cf[i] <= ki)
{
a[++zz]=cf[i]*valuei;//zz是一个指针,指向当前地址
ki-=cf[i];
i++;
}
if (ki > 0)
a[++zz]=ki*valuei;
} int main()
{
int i,j;
for (i=1;i<=6;i++)
{
scanf("%d",&fm[i]);
sum+=fm[i]*value[i];//最高价值
fj(fm[i],value[i]);
}
f[0]=1;
for (i=1;i<=zz;i++)
for (j=sum; j>=a[i];j--)
f[j]=f[j] || f[j - a[i]];//只是一个普通的01背包
for (i=1;i<=sum;i++)
if (f[i])
total++;
printf("%s%d","Total=",total);
return 0;
}

“`