饭卡

https://vjudge.net/problem/18374/origin

之前一直理解错了是先买最小的后最后减最大的这样血赚【大佬粗话】

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 using namespace std;
 6 const int maxn =2005;
 7 int m,n;
 8 int main()
 9 {
10      while(~scanf("%d",&n))
11      {
12          if(n==0) break;
13          int w[maxn];
14          int f[maxn]={0},mx;
15          for(int i=1;i<=n;i++){
16             scanf("%d",&w[i]);
17          }
18          sort(w+1,w+1+n);
19          mx=w[n];
20          scanf("%d",&m);
21         if(m<5) printf("%d
",m);
22         else
23         {
24             m-=5; //用5元买最贵的==金额在买完其他的后无限接近于5元时
25             for(int i=1;i<n;i++) //用n-1个数，m-5来01背包
26             for(int k=m;k>=w[i];k--)
27             f[k]=max(f[k],f[k-w[i]]+w[i]);
28             printf("%d
",m-f[m]+5-mx);
29         }
30         printf("
");
31      }
32   return 0;
33 }

hdu 2546