hdu 5410 CRB and His Birthday(01背包+完全背包)

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=5410

解題思路：

官方題解：

We use dynamic programming to get optimal solution.

Presents with same prices can be considered in groups.

In each group, it is needed to get the maximum number of candies that can be got when k presents are bought.

We sort the presents in non-increasing order of Ai+BiAi+Bi.

Let MAMA be the maximum of AiAi, tt be the minimum of index ii which satisfies inequality Ai+Bi<MAAi+Bi<MA.

We use following strategy.

If k\ <\ tk < t, then for every index from 1 to kk, buy one of that kind and get (A1+B1)+...+(Ak+Bk)(A1+B1)+...+(Ak+Bk) candies.

Else we buy one present for each index\in∈[1...tt] and (k-t)(k−t) presents of that kind whose AA value equals MAMA. In this case we get (A1+B1)+...+(At+Bt)+(k-t)MA(A1+B1)+...+(At+Bt)+(k−t)MA candies.

Let dp[n][m]dp[n][m] be the optimal value we can get passing through nn groups with mm Won.

dp[n][m]\ =\ max(dp[n-1][m-k\times\ w[n]]\ +\ opt[n][k])\ (0\ \leq \ k\ \leq \ m / w[n])dp[n][m] = max(dp[n−1][m−k× w[n]] + opt[n][k]) (0 ≤ k ≤ m/w[n]).

(opt[n][k]opt[n][k]: the maximum number of candies we can get when we buy kk presents of nn-th group, w[n]w[n]: the price for nn-th group)

Time complexity:O(N\times \ (M/1\ +\ M/2\ +...+\ M/M))\ =\ O(NM\cdot logM)O(N× (M/1 + M/2 +...+ M/M)) = O(NM⋅logM)

首先考慮b[i]存在的情況，b[i]隻會出現在第一次購買商品的時候用上，用01背包處理，然後01背包處理完後，接着跑一遍多重背包，這次僅考慮a[i]對最終結果的影響，最終輸出dp[m]即為最終結果。

為什麼可以這樣呢？因為01背包僅僅是考慮第一次買的情況，在01背包之後跑多重背包，狀态是建立在01背包的基礎之上，而這正是我們需要的狀态。。。

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int dp[2005];
int val[1005];
int a[1005],b[1005];

int main(){
    int T;
    int n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&m,&n);
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d%d%d",&val[i],&a[i],&b[i]);
        for(int i = 1; i <= n; i++)
            for(int j = m; j >= val[i]; j--)
                dp[j] = max(dp[j],dp[j-val[i]]+a[i]+b[i]);
        for(int i = 1; i <= n; i++)
            for(int j = val[i]; j <= m; j++)
                dp[j] = max(dp[j],dp[j-val[i]]+a[i]);
        printf("%d\n",dp[m]);
    }
    return 0;
}