题解 P2347 【砝码称重】

zhongtaiyang · 2017-09-14 22:54:45 · 题解

首先声明一下：此题测试数据太水了，以致于六个for循环都能过，我想讲一下这道题的最完美做法。

首先，观察题目，不难发现这是一个多重背包问题（背包总容量是一定的，每一个物品有规定的最多使用次数，求最多的质量和）。对于多重背包问题，常规想法是把有数量限制的物品分成若干件同样的物品，这样就转化成了基础的01背包问题，然而，这样会耗费过高的时间和空间复杂度，据传，最高复杂度甚至可能达到n的立方，就在此时，以倍增算法为思想基础的二进制拆分储存方法也就相应地出现了（即把物品的数量x拆成2的0次方加2的1次方……再加上剩下的那个数），就此，多重背包问题在二进制拆分的数据存储支撑下完美地被我们转化为了多重背包问题，至于怎么输出答案，只要把1到总重量的每一个数都扫一遍，有几个在当前砝码重量下可以取到此砝码的值，答案就是几。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
const int mass={0,1,2,3,5,10,20};//砝码质量
int max;//此为背包的最大载重
int k=0;//用来记录拆分后的数量
int num[20];//用来存放砝码的数量
int c[4000];//用来存放拆分后砝码的质量
int dp[4000];//用来存放在ig中的最大质量
int sum;//用来记录答案
int main()
{
    for(int i=1;i<=6;i++)
    {
        cin>>num[i];
        m+=num[i]*mass[i];
    }
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=num[i];j*=2)//开始关键的二进制拆分
        {
            c[k]=j*mass[j];
            num[i]-=j;
            k++;
        }
        if(num[i])
        {
            c[k]=num[i]*mass[i];
            k++;
        }

}//二进制拆分完成，现在变成了一个简单的01背包问题

    for(int i=1;i<=k;i++)
    {
        for(int j=m;j>=c[i];j--)
            dp[j]=max(dp[j],dp[j-c[i]]+c[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(dp[i]==i)    sum++;
    }
    printf("Total=%d\n",sum);
    return 0;
}