HDUOJ---2546 饭卡

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstring>
 4 #define maxn 1005
 5 using namespace std;
 6 int dp[maxn],flag;
 7 int max(int a,int b)
 8 {
 9     return a>b?a:b;
10 }
11 void zeroonepack(int cost ,int total)
12 {
13     for(int i=total;i>=cost;i--)
14     {
15         dp[i]=max(dp[i],dp[i-cost]+cost);
16     }
17 }
18 
19 int main()
20 {
21    int n,m,i;
22    while(cin>>n,n)
23    {
24        memset(dp,0,sizeof dp);
25        vector<int>arr(n);
26    for(i=0;i<n;i++)
27    {
28        cin>>arr[i];
29        if(i==0||arr[flag]<arr[i])         //找出最贵的那道菜...
30            flag=i;
31    }
32    cin>>m;
33    if(m<5)
34    {
35        cout<<m<<endl;
36        continue;
37    }
38    m-=5;                         //预留5元，用剩下的钱去买最多的菜
39    for(i=0;i<n;i++)
40    {
41        if(flag==i)  continue;    //那道最贵的菜，就不需要比较了！！,最后定然是要吃的
42        zeroonepack(arr[i],m);
43    }
44 
45    cout<<m+5-arr[flag]-dp[m]<<endl;
46    }
47    return 0;
48 }