HDU 4508 湫湫系列故事——减肥记I(全然背包)
http://acm.hdu.edu.cn/showproblem.php?pid=4508
题意:
有n种食物, 每种食物吃了能获得val[i]点幸福度和cost[i]点热量, 如今湫湫每天吃东西的热量不能超过m点. 问她最多能获得多少点幸福度?
分析:
基础的全然背包问题.
本题的限制条件是: 热量总量<=m
本题的目的条件是: 幸福度越大越好.
所以我们令dp[i][j]==x表示仅仅吃前i种食物且总热量不超过j时能获得的最大幸福度为x.
初始化: dp全为0.
状态转移: dp[i][j] = max( dp[i-1][j] , dp[i][j-cost[i]]+val[i])
前者表示第i种物品一个都不选, 后者表示至少选1个第i种物品.
终于所求: dp[n][m].
程序实现用的滚动数组逆序递推, 所以dp仅仅有[j]这一维.
AC代码:
}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5238251.html，如需转载请自行联系原作者
