POJ - 1276 二进制优化多重背包为01背包

题意：直接说数据，735是目标值，然后3是后面有三种钱币，四张125的，六张五块的和三张350的。

思路：能够轻易的看出这是一个多重背包问题，735是背包的容量，那些钱币是物品，而且有一定的数量，是多种背包。但是做的时候总是超时。可能是因为m和n太大。然后可以通过二进制把它转化为01背包，因为将钱币的数量化为二进制，1 2 4直到数量减一。化成的二进制数字排列组合，可以组成任意钱币数量内的数字。

看代码：

//二进制优化  多重背包转化为01背包

#include<stdio.h>

int main()

{

    int cash,s[100010],n;

    int dp[100010];

    while(~scanf("%d%d",&cash,&n))

    {

        for(int i=0;i<=cash;i++)

            dp[i]=0;

        int k=0,a,b;

        for(int i=0;i<n;i++)

        {

            scanf("%d%d",&a,&b);//4 125

            int t=1;

            while(t<a)//转化为1*125 2*125 的背包

            {

                s[k++]=t*b;

                a=a-t;

                t*=2;

            }

            if(a)

                s[k++]=a*b;//1*125剩余的背包

        }

        for(int i=0;i<k;i++)

        {

            for(int j=cash;j>=s[i];j--)

            {

                dp[j]=dp[j]>dp[j-s[i]]+s[i]?dp[j]:dp[j-s[i]]+s[i];

            }

        }

        printf("%d\n",dp[cash]);

    }

    return 0;

}

巴特西

POJ - 1276 二进制优化多重背包为01背包

最新文章

热门文章