hdu 2546饭卡

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<vector>
 4 #include<stdlib.h>
 5 #include<string.h>
 6 #include<iterator>
 7 #include<iostream>
 8 #include<algorithm>
 9 #include<set>
10 #include<map> 
11 using namespace std;
12 
13 int dp[3005],cost[3005];
14 
15 int main()
16 {
17     int n,money,max_cost;
18     while(scanf("%d",&n) && n!=0)
19     {
20         memset(cost,0,sizeof(cost));
21         memset(dp,0,sizeof(dp));
22         for(int i=1;i<=n;i++)
23             scanf("%d",&cost[i]);
24         scanf("%d",&money);
25         
26         sort(cost+1,cost+n+1);
27         
28         max_cost=cost[n];
29         
30         if(money<5)
31             printf("%d\n",money);
32         
33         else
34         {
35             for(int i=1;i<n;i++)       //----------注意是n-1因为最大的n已经取走 
36                 for(int j=money-5;j>=cost[i];j--)
37                     dp[j]=max(dp[j],dp[j-cost[i]]+cost[i]);
38             
39             printf("%d\n",money-max_cost-dp[money-5]);
40         }
41     }
42     return 0;
43 }