luogu1776宝物筛选

多重背包问题

一开始我们的转移方程是

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

    for(int j=m;j>=w[i];j--)

        for(int k=;k<=c[i];k++)

            if(j-k*w[i]>)dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);

然后我们发现T了

有一个简单的优化最内层k是从0-c[i]相当于一条链对于一条链我们很容易想到倍增

然后我们优化：

对于第i个物品，我们把它拆成若干份：取1个取2个取4个取8个 ... 取2^(一大堆)个取剩下的那么多个

这样可以把最内层循环变成log

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

int n,w;

int f[];

int main()

{

    scanf("%d%d",&n,&w);

    while(n--)

    {

        int i,j;

        int Value,weight,m;

        scanf("%d%d%d",&Value,&weight,&m);

        for(i=;((<<(i+))-)<=m;i++)

            for(j=w;j>=(weight<<i);j--)f[j]=max(f[j],f[j-(weight<<i)]+(Value<<i));

        weight=weight*m-(weight<<i)+weight;Value=Value*m-(Value<<i)+Value;

        if(weight>)

            for(j=w;j>=weight;j--)f[j]=max(f[j],f[j-weight]+Value);

    }

    printf("%d",f[w]);

}

巴特西

luogu1776宝物筛选

最新文章

热门文章