希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

背包系列 POJ——1276 多重背包

#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>

int inline MAX(int a,int b)
{
    if(a>b) return a;
    else return b;
}
int N[15],D[15],dp[100010];

int main()
{
    int n,i,j,k,amt,cash;
    while(scanf("%d%d",&cash,&n)==2)
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;++i)
        {
            scanf("%d%d",&N[i],&D[i]);
            dp[D[i]]=D[i];
        }
        for( i =0 ;i < n ;++ i)
        {
            if(D[ i ]*N[ i ]>=cash)//该物品最多超过了总容量，完全背包
            {
                for( j = D[i]; j<=cash  ; ++j)//j由小变大，因为每件物品个数有无限个，可重复放入！！<=中=不可少，否则WA
                    dp[j]=MAX(dp[j],dp[ j - D[i] ]+D[i]);
            }
            else//多重背包
            {
                k=1;
                amt=N[i] ;
                while( k < amt )
                {
                    for( j = cash ; j >=k* D[i] ; --j)//j由大变小，因为后面的先改变后不会影响前面的，反之则不行！！
                        dp[j]=MAX(dp[j],dp[ j - D[i]*k ]+D[i]*k);
                    amt-=k;
                    k*=2;
            
                }
                for( j = cash ; j >=amt* D[i] ; --j)
                        dp[j]=MAX(dp[j],dp[ j - amt*D[ i ] ]+amt*D[ i ]);//头开始理解偏差，正确理解：amt现为分解为2^k后剩下的散量，
                                                                                                                //即可供使用的物品数
            }
        }
        printf("%d\n",dp[cash]);
    }
    return 0;
}

posted on 2011-08-02 11:00 拥梦的小鱼 阅读(396) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理