Ahui Writes Word
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1052Accepted Submission(s): 399
Problem Description
We all know that English is very important, so Ahui strive for this in order to learn more English words. To know that word has its value and complexity of writing (the length of each word does not exceed 10 by only lowercase letters),
Ahui wrote the complexity of the total is less than or equal to C.
Question: the maximum value Ahui can get.
Note: input words will not be the same.
Input
The first line of each test case are two integer N , C, representing the number of Ahui’s words and the total complexity of written words. (1 ≤ N ≤ 100000, 1 ≤ C ≤ 10000)
Each of the next N line are a string and two integer, representing the word, the value(Vi ) and the complexity(Ci ). (0 ≤ Vi , Ci ≤ 10)
Output
Output the maximum value in a single line for each test case.
Sample Input
5 20
go 5 8
think 3 7
big 7 4
read 2 6
write 3 5
Sample Output
15
Hint
Input data is huge,please use “scanf(“%s”,s)”
Author
Ahui
Source
Recommend
notonlysuccess
题意 :
多重背包 多重的含义 是指同种的东西有一定的个数 即有相同的东西出现 对于相同的每个都可以取一次 可以同时取
题目意识是 输入 单词个数n 总的消耗c
再输入不同的单词 以及每个单词的价值和消耗 (这个字符串起不到任何作用 在本题中)
问能得到的最大价值
思路
本题主要卡人的地方是数据大 有可能会超时
有100000个
但是可以看到物品的价值可以和消耗最多为10 那么总共才100中物品
所以每种物品都可能有很多重复的
所以要二进制优化一下
#include<stdio.h>
#include<string.h>
struct haha
{
int v;
int val;
}a[100010];
int map[105][105];
int bag[10010],v;
void _01bag(int n)
{
int i,j;
memset(bag,0,sizeof(bag));
for(i=0;i<n;i++)
for(j=v;j>=a[i].v;j--)
if(bag[j]<bag[j-a[i].v]+a[i].val)
bag[j]=bag[j-a[i].v]+a[i].val;
printf("%d\n",bag[v]);
}
int main()
{
int n,x,y,i,j,k,temp;
char s[20];
while(scanf("%d %d",&n,&v)!=EOF)
{
memset(map,0,sizeof(map));
for(i=1;i<=n;i++)
{
scanf("%s %d %d",s,&x,&y);//x是val y是v
map[x][y]++;
}
k=0;
for(i=0;i<=10;i++)
for(j=0;j<=10;j++)
{
if(map[i][j]==0) continue;
temp=1;
while(map[i][j]>temp)
{
a[k].v=j*temp;
a[k++].val=i*temp;
map[i][j]-=temp;
temp=temp*2;
}
a[k].v=j*map[i][j];
a[k++].val=i*map[i][j];
}
_01bag(k);
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类