計蒜客/节食的限制(01背包)

題目鏈接: https://nanti.jisuanke.com/t/227

題意:中文題誒~

思路:01背包

類似的題: http://www.cnblogs.com/geloutingyu/p/6279279.html

用dp[i][j]表示到地 i 個數能得到的不大於 j 的最大的數, 顯然有 dp[i-1][j-a[i]]+a[i] 爲選擇第 i 個與元素能得到的不大於 j 的最大的數, 那麼有動態轉移方程:

 if(j>=a[i]) dp[i][j]=max(dp[i-1][j], dp[i-1][j-a[i])+a[i])

 else dp[i][j]=max(dp[i][j], dp[i-1][j])

然而本題有空間限制, 開不了二維, 那也簡單. 從上面的動態轉移方程式可以發現只用了上一層循環的數據, 顯然前面的數據是可以不用存儲的；

用dp[j]存儲到當前元素可以得到的不大於 j 的最大的數, 顯然當前數組存儲的是上一層循環的數據, 那麼只要從後往前用本層循環的數據覆蓋上層數據即可；

動態轉移方程式爲:

 dp[j]=max(dp[j], dp[j-x]+x]

代碼:

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAXN=1e5+10;
int dp[MAXN];//dp[j]存儲前i個元素能達到不大於j的最大值

int main(void){
    int x, h, n, ans=0;
    scanf("%d%d", &h, &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &x);
        for(int j=h; j>=x; j--){
            dp[j]=max(dp[j], dp[j-x]+x);
        }
    }
    printf("%d
", dp[h]);
    return 0;
}