首页 > 代码库 > hdu3732(多重背包)

hdu3732(多重背包)

2024-08-10 14:53:06   218人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3732

 

题意：Ahui学习英语单词，每个单词都是不同的，并且都有自身的价值量 w 和难度值 c （0<=w,c<=10），Ahui 现在给定总单词个数 N 和可以总难度值 V，求最大的价值。

 

分析：01背包复杂度为O（NV），这样必超时，由于w，c较小，这样对于在N<=100000个物品中必定有很多价值和难度相同的单词，由此可变为有至多（11*11）种物品，每种物品有x个，求在容量为v的背包至多能装多大价值的物品。如此便可转化为二进制优化的多重背包，这个复杂度为O(V*log(N)).

 

技术分享
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;int value[N],weight[N],dp[N];int hash[11][11],n,v,tot;int solve(){    clr(dp);    for(int i=1;i<tot;i++)    {        for(int j=v;j>=weight[i];j--)            dp[j]=max(dp[j-weight[i]]+value[i],dp[j]);    }    return dp[v];}int main(){    while(scanf("%d%d",&n,&v)>0)    {        clr(hash);        for(int i=1;i<=n;i++)        {            char s[100];            int x,y;            scanf("%s%d%d",s,&x,&y);            hash[x][y]++;        }        tot=1;        for(int i=0;i<=10;i++)        for(int j=0;j<=10;j++)        {            if(hash[i][j])            {                for(int k=1;k<=hash[i][j];k*=2)                {                    value[tot]=i*k;                    weight[tot++]=j*k;                    hash[i][j]-=k;                }                if(hash[i][j])value[tot]=hash[i][j]*i,weight[tot++]=hash[i][j]*j;            }        }        int ans=solve();        printf("%d\n",ans);    }}
View Code

 

hdu3732(多重背包)


联系
我们