HDU 2546 饭卡

题解：贪心思想，去除一个最大值，背包容量减5，直接01背包即可。

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
int main()  
{  
    int n,m;  
    while(scanf("%d",&n),n!=0){       
        int a[1005];  
        memset(a,0,sizeof(a));  
        for(int i=1;i<=n;i++)  
            scanf("%d",&a[i]);  
        sort(a+1,a+n+1);    
        scanf("%d",&m);  
        if(m<5)printf("%d
",m);  
        else{  
          int f[1005]; 
          memset(f,0,sizeof(f));  
          for(int i=1;i<=n-1;i++)  
            for(int j=m-5;j>=a[i];j--)     
              if(f[j]<f[j-a[i]]+a[i])  
                 f[j]=f[j-a[i]]+a[i];  
         printf("%d
",m-a[n]-f[m-5]);  
        }         
    }     
    return 0;  
}