二次背包问题

quadknap.cpp

/*
 * 二次背包问题
 *
 *  Created on: 2012-4-19
 *      Author: Calvin
 */
#include <iostream>
#include <vector>
#include <windows.h>
using namespace std;

//物品的价值、重量、体积
struct Object{
	int v;
	int w;
	int b;
	};
//背包的容量和容积
struct Knapsack{
	int v;
	int c;
	int d;
		};
void quadknap(int n, Knapsack kp, vector<Object> obj, int*** &m);
void traceback(int*** &m, int n, vector<int>& x, Knapsack kp, Knapsack &kk, vector<Object> obj);
void make3DArray(int*** &x, int d1, int d2, int d3);
int main()
{
	//物品种类
	unsigned int n=0;
	vector<Object> obj;
	Knapsack kp;
	//输入测试数据
	cout<<"\t"<<"二次背包问题"<<endl;
	cout<<"================================="<<endl;
	cout<<"使用默认测试数据 or 手动输入数据？"<<endl;
	cout<<"（默认数据请按0，手动输入请按1）"<<endl;
	cout<<"================================="<<endl;
	int flag=0;
	cin>>flag;
	if(flag)
	{
		cout<<"请输入背包容量：";
		cin>>kp.c;
		cout<<"请输入背包容积：";
		cin>>kp.d;
		int a,b,c;
		cout<<"================================="<<endl;
		cout<<"分别输入测试物品的价值、重量和体积"<<endl;
		cout<<"（至少输入两组，输入-1<enter>结束）"<<endl;
		while(true)
		{
			cout<<"================================="<<endl;
			cout<<"请输入第"<<obj.size()+1<<"组三个数"<<endl;
			cin>>a;
			if(a<=0) break;
			cin>>b;
			if(b<=0) break;
			cin>>c;
			if(c<=0) break;
			Object ob={a,b,c};
			obj.push_back(ob);
		}
	}
	else
	{
		Object ob1={4,3,2};
		Object ob2={5,4,3};
		Object ob3={6,5,4};
		Object ob4={7,6,5};
		obj.push_back(ob1);
		obj.push_back(ob2);
		obj.push_back(ob3);
		obj.push_back(ob4);
		//背包的容量和容积
		kp.v=0;
		kp.c=15;
		kp.d=15;
	}
	system("cls");
	n=obj.size();
	//输入少于两组自动退出
	if(n<3) exit(0);
	//定义三维数组
	int*** m;
	make3DArray(m, n+1, kp.c+1, kp.d+1);
	quadknap(n, kp, obj, m);
	vector<int> x;
	Knapsack kk={0,0,0};
	traceback(m, n, x, kp, kk, obj);
	cout<<"\t"<<"二次背包问题"<<endl;
	cout<<"============================"<<endl;
	cout<<"背包容量: "<<kp.c<<"\t"<<"背包容积: "<<kp.d<<endl;
	cout<<"============================"<<endl;
	cout<<n<<"组测试数据为"<<endl;
	cout<<"============================"<<endl;
	cout<<"编号"<<"\t"<<"价值"<<"\t"<<"重量"<<"\t"<<"体积"<<endl;
	int num=1;
	for(unsigned int i=0;i<obj.size();i++)
		cout<<num++<<"\t"<<obj[i].v<<"\t"<<obj[i].w<<"\t"<<obj[i].b<<endl;
	cout<<"============================"<<endl;
	cout<<"最优解x向量为"<<endl;
	for(unsigned int i=0; i<x.size(); i++)
		cout<<x[i]<<"\t";
	cout<<endl;
	cout<<"============================"<<endl;
	cout<<"最大值为"<<endl;
	cout<<"价值"<<"\t"<<"重量"<<"\t"<<"体积"<<endl;
	cout<<kk.v<<"\t"<<kk.c<<"\t"<<kk.d<<endl;
	cout<<"============================"<<endl;
	system("pause");
	//cin.get();
	return 0;
}
//计算每一步的最大值
void quadknap(int n, Knapsack kp, vector<Object> obj, int*** &m)
{
	//递归初始条件
	int t = max(obj[n-1].w, obj[n-1].b);
	for (int i = 1; i < t; i++) {
		for (int j = 1; j < t; j++) {
			m[n][i][j] = 0;
		}
	}
	for (int i = t; i <= kp.c; i++)
		for (int j = t; j <= kp.d; j++)
			m[n][i][j] = obj[n-1].v;

	for (int i = n-1; i > 1; i--)
	{
		t = max(obj[i-1].w, obj[i-1].b);
		for (int j = 1; j < t; j++)
			for (int k = 1; k < t; k++)
				m[i][j][k] = m[i + 1][j][k];
		for (int j = t; j <= kp.c; j++)
			for (int k = t; k <= kp.d; k++)
				m[i][j][k] = max(m[i + 1][j][k],m[i + 1][j - obj[i-1].w][k - obj[i-1].b] + obj[i-1].v);
	}

	m[1][kp.c][kp.d] = m[2][kp.c][kp.d];
	if (m[2][kp.c - obj[0].w][kp.d - obj[0].b] + obj[0].v > m[1][kp.c][kp.d]) {
		m[1][kp.c][kp.d] = m[2][kp.c - obj[0].w][kp.d - obj[0].b] + obj[0].v;
	}
}
//获得最优解
void traceback(int*** &m, int n, vector<int>& x, Knapsack kp, Knapsack &kk, vector<Object> obj)
{
	//m[0][kp.c][kp.d]=0;
	for(int i=1; i<n; i++)
		if(m[i][kp.c][kp.d]==m[i+1][kp.c][kp.d])
			x.push_back(0);
		else
		{
			x.push_back(1);
			kk.c+=obj[i-1].w;
			kk.d+=obj[i-1].b;
			kk.v+=obj[i-1].v;
		}
		if(m[n][kp.c][kp.d])
		{
			x.push_back(1);
			kk.c+=obj[n-1].w;
			kk.d+=obj[n-1].b;
			kk.v+=obj[n-1].v;
		}
		else
			x.push_back(0);
}
//动态生成三维数组
void make3DArray(int*** &x, int d1, int d2, int d3)
{
	x=new int**[d1];
	for(int i=0; i<d1; i++)
	{
		x[i]=new int*[d2];
		for(int j=0; j<d2; j++)
			x[i][j]=new int[d3];
	}
}