hdu2546　饭卡　　　　０１背包

link:http://acm.hdu.edu.cn/showproblem.php?pid=2546

也算一个贪心的想法吧．

先把总钱数减去５，再把价值最大的挑出来．然后用０１背包．最终买下挑出来的那个价值最大的商品．这样的话，我就实现了最终用最少的钱数买了价值最多的商品，剩下钱数当然也是最少了．

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <cctype>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <deque>
10 #include <queue>
11 #include <list>
12 #include <map>
13 #include <set>
14 #include <vector>
15 #include <utility>
16 #include <functional>
17 #include <fstream>
18 #include <iomanip>
19 #include <sstream>
20 #include <numeric>
21 #include <cassert>
22 #include <ctime>
23 #include <iterator>
24 const int INF = 0x3f3f3f3f;
25 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
26 using namespace std;
27 int main(void)
28 {
29     ios::sync_with_stdio(false);
30     int n, V;
31     int c[1111], f[1111];
32     #ifndef ONLINE_JUDGE
33     freopen("in.txt", "r", stdin);
34     #endif // ONLINE_JUDGE
35     while (cin>>n)
36     {
37         if(!n) break;
38         for (int i = 0; i < n; ++i) cin>>c[i];
39         cin>>V;
40         V-=5;
41         if (V<0)
42         {
43             cout<<V+5<<endl; continue;
44         }
45         int tmp=-1, Max;
46         for (int i = 0; i <n; ++i)
47             if(tmp<c[i]) tmp=c[i], Max=i;
48         memset(f,0,sizeof(f));
49         for (int i=0;i<n;++i)
50         {
51             if (i==Max) continue;
52             for (int v = V; v>=c[i]; --v)
53             {
54                 f[v] = max(f[v], f[v-c[i]]+c[i]);
55             }
56         }
57         cout<<V+5-f[V]-c[Max]<<endl;
58     }
59     return 0;
60 }

囧

hdu2546 饭卡 ０１背包

hdu2546　饭卡　　　　０１背包