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

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代码:

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=100000+5; int n; //物品种数 int cost[100+5];//热量值 int val[100+5]; //幸福度 int m; //热量限制 int dp[maxn]; int main() { while(scanf("%d",&n)==1) { for(int i=1;i<=n;i++) scanf("%d%d",&val[i],&cost[i]); scanf("%d",&m); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=cost[i];j<=m;j++) dp[j] = max(dp[j], dp[j-cost[i]]+val[i]); } printf("%d\n",dp[m]); } return 0; }