hdu2546 饭卡 ０１背包

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

也算一个贪心的想法吧．

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

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <cctype>

 #include <algorithm>

 #include <queue>

 #include <deque>

 #include <queue>

 #include <list>

 #include <map>

 #include <set>

 #include <vector>

 #include <utility>

 #include <functional>

 #include <fstream>

 #include <iomanip>

 #include <sstream>

 #include <numeric>

 #include <cassert>

 #include <ctime>

 #include <iterator>

 const int INF = 0x3f3f3f3f;

 const int dir[][] = {{-,},{,},{,-},{,},{-,-},{-,},{,-},{,}};

 using namespace std;

 int main(void)

 {

     ios::sync_with_stdio(false);

     int n, V;

     int c[], f[];

     #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     while (cin>>n)

     {

         if(!n) break;

         for (int i = ; i < n; ++i) cin>>c[i];

         cin>>V;

         V-=;

         if (V<)

         {

             cout<<V+<<endl; continue;

         }

         int tmp=-, Max;

         for (int i = ; i <n; ++i)

             if(tmp<c[i]) tmp=c[i], Max=i;

         memset(f,,sizeof(f));

         for (int i=;i<n;++i)

         {

             if (i==Max) continue;

             for (int v = V; v>=c[i]; --v)

             {

                 f[v] = max(f[v], f[v-c[i]]+c[i]);

             }

         }

         cout<<V+-f[V]-c[Max]<<endl;

     }

     return ;

 }

囧