knapsack.cpp

动态规划算法求解0-1背包问题,动态规划算法knapsack求最优值

////动态规划算法knapsack求最优值
#include <iostream>
#include<iomanip>
#include<string.h>
using namespace std;


//返回w和c的最小值
int min(int w,int c)
{
	int temp;
	if (w < c)
		temp = w;
	else
		temp = c;
	return temp;
}

//返回w和c的最大值
int max(int w,int c)
{
	int temp;
	if (w>c) 
		temp=w;
	else
		temp=c;
	return temp;
}

//动态规划算法knapsack求最优值
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;					// J >= Wn : m[n][j] = Vn
	for(int j = w[n]; j <= c; j++)
		m[n][j] = v[n];				//  0 =< J <= Wn : m[n][j] = 0;

	for(int i = n-1; i > 1; i--)   //递归部分
	{
		jmax = min(w[i] - 1,c);

		for(int j = 0; j <= jmax; j++)
			m[i][j] = m[i+1][j];			//  0 =< j <= Wi : m[i][j] = m[i+1][j]

		for(int j = w[i]; j <= c; j++)
			m[i][j] = max(m[i+1][j], m[i+1][j - w[i]] + v[i]);  // j >= Wi: m[i][jj] = max(m[i+1][jj], m[i+1][jj - 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]);

	cout<<"最优值："<<m[1][c]<<endl;

	for(int l = 2; l <= n ;l++)
	{
		for(int j = 0; j<= c ;j++)
		{
			cout<<m[l][j]<< "  ";		
		} 

		cout << endl;
	}
}


///回代法求最优解
int 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;
	}

	cout<<"最优解:"<<endl;
	for(int y = 1; y <= n;y++)
	{
		cout<<setw(5)<<x[y];  //打印的数据如果不足5位就补足5位
	}

	cout<<endl;
	return x[n];

}

void main()
{
	int n,c;
	int **m;

	cout<<"动态规划算法求解0-1背包问题"<<endl;

	cout<<"请输入物品个数和重量上限:";
	cin>>n>>c;
	int *v=new int[n+1];

	cout<<"Pls input the property (v[i]):"<<endl;
	for(int i=1;i<=n;i++)
		cin>>v[i];
	int *w=new int[n+1];

	cout<<"Pls input the weight (w[i]):"<<endl;

	for(int j=1;j<=n;j++)
		cin>>w[j];

	int *x=new int[n+1];
	m = new int*[n+1];   //动态的分配二维数组

	for(int p = 0; p < n+1; p++)
	{
		m[p] = new int[c+1];
	} 

	cout<<"Knapsack:"<<endl;
	knapsack(v,w,c,n,m);

	cout<<"traceback:"<<endl;
	traceback(m,w,c,n,x);

}