Ahui Writes Word

5 20
go 5 8
think 3 7
big 7 4
read 2 6
write 3 5

15

解题思路：数据量太大，可以转换为多重背包问题，转换后再将多重背包用2进制优化成0-1背包问题。

              #include<iostream><br /> #include<cstring><br /> #include<cstdio><br /> using namespace std;<br /> int p[15000];<br /> int w[15000];<br /> int f[10005];<br /> int map[15][15];<br /> int main()<br /> {<br /> int n,c,i,j,x,y,k,t,sum;<br /> char s[100];<br /> while(scanf("%d%d",&n,&c)!=EOF)<br /> {<br /> memset(map,0,sizeof(map));<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%s%d%d",s,&x,&y);<br /> map[x][y]++;//记录价值和复杂度都相同的单词个数<br /> }<br /> k=1;<br /> for(i=0;i<=10;i++)<br /> for(j=0;j<=10;j++)<br /> {<br /> if(map[i][j]>=1)<br /> {<br /> sum=1,t=1;<br /> while(sum<=map[i][j])//用1，2，4，…，2^k 将多重背包转化为0-1背包。 如13=1+2+4+6<br /> {<br /> p[k]=t*i;<br /> w[k++]=t*j;<br /> t*=2;<br /> sum+=t;</p> <p> }<br /> if(sum-t<map[i][j])<br /> {<br /> p[k]=i*(map[i][j]-sum+t);<br /> w[k++]=j*(map[i][j]-sum+t);<br /> }<br /> //printf("%d %d ",i,j);<br /> }<br /> }<br /> memset(f,0,sizeof(f));<br /> for(i=1;i<k;i++)<br /> {<br /> for(j=c;j>=w[i];j--)<br /> {<br /> if(f[j]<f[j-w[i]]+p[i])<br /> f[j]=f[j-w[i]]+p[i];<br /> }<br /> }<br /> printf("%d/n",f[c]);<br /> }<br /> return 0;<br /> }<br />