首页 > 其他 > 详细

HDU 4508 湫湫系列故事——减肥记I (完全背包)

时间:2014-03-17 13:02:56      阅读:380      评论:0      收藏:0      [点我收藏+]

题意:有n种食物,每种食物可以给湫湫带来一个幸福感a,同时也会给她带来b的卡路里的摄入,然后规定她一天摄入的卡路里的量不能超过m,一共有n种食物,问可以得到的

最大的幸福感是多少?

解题报告:一开始以为是01背包,没看题,然后发现题目里面没有说每种食物只能吃一次,才发现是个完全背包,一开始还以为题目的第二组测试数据是错的,无语。。。

bubuko.com,布布扣
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int a[105],b[105],ans[100005];
 8 
 9 int main()
10 {
11     int n,m;
12     while(scanf("%d",&n)!=EOF)
13     {
14         for(int i = 0;i < n;++i)
15         scanf("%d%d",&a[i],&b[i]);
16         scanf("%d",&m);
17         memset(ans,0,sizeof(ans));
18         for(int i = 0;i < n;++i)
19         for(int k = 1;k <= m / b[i];++k)
20         for(int j = m;j >= k * b[i];--j)
21         ans[j] = max(ans[j],ans[j-k * b[i]] + k * a[i]);
22         int Mtot = ans[0];
23         for(int i = 0;i <= m;++i)
24         Mtot = max(ans[i],Mtot);
25         printf("%d\n",Mtot);
26     }
27     return 0;
28 }
View Code

HDU 4508 湫湫系列故事——减肥记I (完全背包),布布扣,bubuko.com

HDU 4508 湫湫系列故事——减肥记I (完全背包)

原文:http://www.cnblogs.com/xiaxiaosheng/p/3602796.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!