即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

多重背包(二进制优化optimization)

编程语言 zhuanshunzhe 12℃ 0评论

类似于poj 1014


qduoj

#include
#define maxn 100007

using namespace std;

int mm[20][20];
int dp[maxn];
int v[maxn];
int w[maxn];

int main()
{
    int n,m,t;
    scanf("%d",&t);


    while(t--)
    {
        scanf("%d%d",&n,&m);

        memset(mm,0,sizeof(mm));
        memset(dp,0,sizeof(dp)); 

        int ti,vi;
        for(int i=0;iscanf("%d%d",&ti,&vi);
            mm[ti][vi]++;
        }

        int cnt=1;
        for(int i=1;i<=10;i++)
            for(int j=1;j<=10;j++)
            {
                int tmp = mm[i][j];
                for(int k=1;k<=tmp;k<<=1)
                {
                    v[cnt]=j*k;
                    w[cnt]=i*k;
                    cnt++;
                    tmp-=k;
                }
                if(tmp>0)
                {
                    v[cnt]=j*tmp;
                    w[cnt]=i*tmp;
                    cnt++;
                }
            }
        for(int i=1;ifor(int j=m;j>=w[i];j--)
                dp[j]=max(dp[j-w[i]]+v[i],dp[j]);

        cout<return 0;
}

转载请注明:CodingBlog » 多重背包(二进制优化optimization)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情