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