HDU2546 饭卡(01背包)

题目链接

中文题。

m小于5时直接输出m,否则01背包搞。因为要值最小,所以01背包搞时不考虑最大价格的那个菜,搞完再减去最大价格的菜。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1005];
int w[1005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n, m;
    while(scanf("%d", &n) != EOF && n){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        scanf("%d", &m);
        sort(w+1, w+n+1);
        if(m < 5) cout << m << endl;
        else{
            for(int i = 1; i <= n-1; i++){
                for(int j = m-5; j >= w[i]; j--){
                    dp[j] = max(dp[j], dp[j-w[i]]+w[i]);
                }
            }
            int ans = m-dp[m-5]-w[n];
            cout << ans << endl;
        }
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 01背包  动态规划