cdoj 31 饭卡(card) 01背包

思路：01背包，跑容量为m-5，物品为n-1件的01背包。贪心：用剩下的5元买最贵的

转移：dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+c[i]，滚动优化一下就好了

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1e3+10;
 5 
 6 int c[maxn],dp[50005];
 7 
 8 int main(){
 9     int n,m;
10     while(cin>>n,n){
11         for(int i=1; i<=n; i++)
12             cin >> c[i];
13         cin >> m;
14         if(m<5){   
15             cout<<m<<endl;
16             continue;
17         }
18 
19         sort(c+1,c+1+n);
20         memset(dp,0,sizeof(dp));
21         for(int i=1; i<n; i++){
22             for(int j=m-5; j>=c[i]; j--){
23                 dp[j] = max(dp[j],dp[j-c[i]]+c[i]);
24             }
25         }
26         int ans = m-(dp[m-5]+c[n]);
27         cout << ans << endl;
28     }
29 }