UVA 624(01背包记录路径)

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

 

记录路径可以用一个二维数组，记录改变时的量。然后从后往前可以推得所有的值。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

#define MEM(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define debug printf("!\n")
#define INF 8000
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ep 1e-6

int dp[INF];

int way[INF][INF];//保存路径

int ci[INF];//容量
int wi[INF];//价值
int n,V,i,j,v,t,sum;


void zeroOnePack(int cost,int weight)
{
          for(v = V;v>=cost;v--)
          {
                    dp[v] =MAX(dp[v],dp[v-cost]+weight);
                    if(dp[v]==dp[v-cost]+weight)
                              way[i][v] = 1;
          }
}

int main()
{

          while(sf("%d",&V) && V)
          {

                    MEM(dp,0);
                    MEM(way,0);
                    MEM(wi,0);

                    sf("%d",&n);

                    for(i = n;i>=1;i--)//顺序需要
                    {
                              sf("%d",&wi[i]);
                    }

                    for(i = 1;i<=n;i++)
                    {
                              zeroOnePack(wi[i],wi[i]);
                    }

                    for(i = n,j = dp[V];i>=0,j>0;i--)
                    {
                              if(way[i][j])
                              {
                                        pf("%d ",wi[i]);
                                        j-=wi[i];//改变则检查之前wi[i]的量
                              }
                    }
                    pf("sum:%d\n",dp[V]);

          }
    return 0;
}