01beibao3.cpp

0-1背包问题 将计算出的装入背包物品的最大价值和最优装入方案输出。第一行输出为：Optimal value is

#include<iostream.h>
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
void Knapsack(int *v,int*w,int c,int n,int **m)
{
    int jMax=min(w[n]-1,c);
    for(int j=0;j<=jMax;j++)
        m[n][j] = 0;
    for(j=w[n];j<=c;j++)
        m[n][j]=v[n];
    for(int i=n-1;i>1;i--) 
	{
        jMax=min(w[i]-1,c);
        for (j=0;j<=jMax;j++)
            m[i][j]=m[i+1][j];
        for (j=w[i];j<=c;j++)
            m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
    }
    m[1][c]=m[2][c];
    if (c>=w[1])
        m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void TraceBack(int **m,int *w,int c,int n,int *x)
{
    for (int i=1;i<n;i++) 
	{
        if(m[i][c]==m[i+1][c]) 
			x[i]=0;
        else 
		{
            x[i]=1;
            c-=w[i];
        }
    }
    x[n]=(m[n][c])?1:0;
	for(i=1;i<n+1;i++)
		cout<<x[i]<<' ';
}
int main()
{
    int n,c,i;
	cin>>n>>c;
    int w[6]={-1, 6, 3 ,5 ,4 ,6};
    int v[6] = {-1,2, 2 ,6, 5, 4};
    int **ppm = new int*[n+1];
    for (i=0; i<n+1; i++)
        ppm[i] = new int[c+1];
    int x[6];
    Knapsack(v, w, c, n, ppm);
    TraceBack(ppm, w, c, n, x);
    return 0;
}