hdu 2546 饭卡(0/1背包)

点击打开链接hdu 2546

思路: 贪心+0/1背包
分析:
1 题目中收到只有当余额大于等以5的时候才可以买东西，那么我们利用m-5去买这样保证了于额不会小于5，那么这样就可以买东西了，因为最后可能还有点于额（为0）的时候也是可以买的，那么最后一次就买最贵的这样保证于额最少了。
2 这边我们用到贪心+dp的思想，总体不好想，对于我这种dp弱逼来说没有题解我真不懂（有了题解也不懂）

代码:

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

const int N = 1010;
const int MAXN = N*50;

int n , m , sum;
int v[N] , dp[MAXN];

int solve(){
    memset(dp , 0 , sizeof(dp));
    sort(v+1 , v+1+n);
    sum = m-5;
    for(int i = 1 ; i < n ; i++){
        for(int j = sum ; j >= v[i] ; j--)
            dp[j] = max(dp[j] , dp[j-v[i]]+v[i]); 
    }
    return m-dp[sum]-v[n];
}

int main(){
    while(scanf("%d" , &n) && n){
         for(int i = 1 ; i <= n ; i++) 
             scanf("%d" , &v[i]);
         scanf("%d" , &m);
         printf("%d\n" , m < 5 ? m : solve());
    }
    return 0;
}