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

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;
}