三维0－1背包问题.cpp

动态规划解一系列经典问题

#include <iostream.h>

int min(int x, int y)
{
	if(x >= y)
		return y;
	else
		return x;
}

int max(int x, int y)
{
	if(x >= y)
		return x;
	else
		return y;
}

void Knapsack(int *v, int *w, int c, int *b, int d, int n, int ***m)
{
    int i,j;
	int wMax = min(w[n] - 1, c);
	int bMax = min(b[n] - 1, d);
	for(j = 0; j <= wMax; j++)
		for(i = 0; i <= d; i++)
			m[n][j][i] = 0;
	for(j = 0; j <= bMax; j++)
		for(i = 0; i <= c; i++)
			m[n][i][j] = 0;
	for(j = w[n]; j <= c; j++)
		for(int i = b[n]; i <= d; i++)
			m[n][j][i] = v[n];


	for(int k = n - 1; k > 1; k--)
	{
		wMax = min(w[k] - 1, c);
	    bMax = min(b[k] - 1, d);
		for(j = 0; j <= wMax; j++)
		    for(i = 0; i <= d; i++)
			    m[k][j][i] = m[k + 1][j][i];
	    for(j = 0; j <= bMax; j++)
		    for(i = 0; i <= c; i++)
			    m[k][i][j] = m[k + 1][i][j];
	    for(j = w[k]; j <= c; j++)
		    for(i = b[k]; i <= d; i++)
		    	m[k][j][i] = max(m[k + 1][j][i], m[k + 1][j - w[k]][i - b[k]] + v[k]);
	}

	if(n >= 2){
    	m[1][c][d]=m[2][c][d];
    	if(c >= w[1] && d >= b[1])
	    	m[1][c][d] = max(m[1][c][d], m[2][c - w[1]][d - b[1]] + v[1]);
	}
}

void Traceback(int ***m, int *w, int c, int *b, int d, int n,int *x)
{
	for(int i = 1; i < n; i++)
		if(m[i][c][d] == m[i + 1][c][d]) x[i] = 0;
		else {x[i] = 1; c -= w[i]; d -= b[i];}
	x[n] = (m[n][c][d])?1:0;
}

void main()
{
    int n, c, d;
	int i,j;
	cout<<"enter the number of goods:";
	cin>>n;
	cout<<"enter the capability of the bag:";
	cin>>c;
	cout<<"enter the cubage of the bag:";
	cin>>d;
//////////////////////////////////
	int *w = new int[n + 1];
	w[0] = 0;
	cout<<"enter "<<n<<" number to match the weight of every goods:\n";
	for(i = 1; i <= n; i++)
		cin>>w[i];

	int *b = new int[n + 1];
	b[0] = 0;
	cout<<"enter "<<n<<" number to match the cubage of every goods:\n";
	for(i = 1; i <= n; i++)
		cin>>b[i];

	int *v = new int[n + 1];
	v[0] = 0;
	cout<<"enter "<<n<<" number to match the value of every goods:\n";
	for(i = 1; i <= n; i++)
		cin>>v[i];
/////////////////////////////////////

	int ***m;
	m = new int**[n + 1];
	for(i = 0; i <= n; i++)
		m[i] = new int*[c + 1];
	for(i = 0; i <= n; i++)
		for(j = 0; j <= c; j++)
			m[i][j] = new int[d + 1];
cout<<"rorre"<<endl;
	for(int k = 0; k <= n; k++)
		for(j = 0; j <= c; j++)
			for(i = 0; i <= d; i++)
				m[k][j][i] = 0;

	
////////////////////////////////////////
	int *x = new int[n + 1];
	for(i = 0; i <= n; i++)
		x[i] = 0;
////////////////////////////////////////
	Knapsack(v,w,c,b,d,n,m);
    Traceback(m,w,c,b,d,n,x);

	cout<<"the biggest total value is: "<<m[1][c][d]<<endl;
	cout<<"the state of every goods is(0 reparent NOT IN BAG, 1 reparent IN BAG):\n";
	for(j = 1; j <= n; j++)
		cout<<x[j]<<"\t";
	cout<<endl;
}