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

August 6, 2013
Uva DP

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), 1459917536@qq.com
 *   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-9;
using namespace std;
int V, n, c[22], f[22222], g[22][22222];
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 = 0; i < n; ++i) cin>>c[i];
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for (int i = n-1; i>=0; --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] = 1;
                } else g[i][v] = 0;
            }
        }
        for (int i = 0, 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好用多了，囧

Read more