uva624 CD　　　０１背包+输出最优解

link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=565

用一个二维数组g[i][v]表示：当状态转移到v的时候，第i个物品是不是用到，如果用到标记１，否则标记０．

输出路径的时候，注意，从物品编号０一直到n-1.如果某个物品被用到了，g[i][v]里面的v，就要减去这个物品的体积，然后继续往下找．

 /*
  * =====================================================================================
  *       Filename:  cd.cpp
  *        Created:  04/08/2013 15:21:34
  *         Author:  liuxueyang (lxy), [e-mail]
  *   Organization:  Hunan University
  *
  * =====================================================================================
  */

 /*
 ID: zypz4571
 LANG: C++
 TASK: cd.cpp
 */
 #include <iostream>
 #include <cstdlib>
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <cctype>
 #include <algorithm>
 #include <queue>
 #include <set>
 #include <stack>
 #include <map>
 #include <list>
 #define INF 0x3f3f3f3f
 #define MOD 1000000007
 #define LL long long
 const double eps=1e-;
 using namespace std;
 int V, n, c[], f[], g[][];
 int main ( int argc, char *argv[] )
 {
 #ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
 #endif
     ios::sync_with_stdio(false);
     while (cin>>V) {
         cin>>n;
         for (int i = ; i < n; ++i) cin>>c[i];
         memset(f,,sizeof(f));
         memset(g,,sizeof(g));
         for (int i = n-; i>=; --i) {
             for (int v = V; v>=c[i]; --v) {
                 if (f[v] <= f[v-c[i]]+c[i]) {
                     f[v] = f[v-c[i]]+c[i]; g[i][v] = ;
                 } else g[i][v] = ;
             }
         }
         for (int i = , j = V; i < n; ++i) {
             if (g[i][j]) {
                 cout<<c[i]<<' ';
                 j-=c[i];
             }
         }
         cout<<"sum:"<<f[V]<<endl;
     }
         return EXIT_SUCCESS;
 }                /* ----------  end of function main  ---------- */

再一次表示vim比codeblocks好用多了，囧