main.cpp

来自「计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)」· C++ 代码 · 共 73 行

#include<iostream.h>
#include<stdlib.h>

int min(int x,int y)
{
	if(x<y) return x;
	return y;
}

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

template<class Type>
void Knapsack(Type*v,int* w,int c,int n,Type**m)
{
	//v[1-n]中存储的是n个物体的价值,w[1-n]中存储是n个物体的重量
	//这里假定了w中是整数
	int jMax=min(w[n]-1,c);

	int i,j;

	for(j=0;j<=jMax;j++) m[n][j]=0;
	for(j=w[n];j<=c;j++) m[n][j]=v[n];
	for(j=0;j<=c;j++) cout<<m[n][j]<<",";
	cout<<endl;


	for(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]);
		for(j=0;j<=c;j++) cout<<m[i][j]<<",";
		cout<<endl;

	}

	m[i][c]=m[2][c];
	
	if(c>w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
	for(j=0;j<=c;j++) cout<<m[1][j]<<",";
		cout<<endl;

}

void main()
{
	int n=5;
	
	int c=10;

	int w[]={0,2,2,6,5,4};

	int v[]={0,6,3,5,8,6};

	int **m;
	m=new int*[n+1];
	for(int i=0;i<=n;i++)
		m[i]=new int[c+1];

	Knapsack(v,w,c,n,m);

	cout<<"The result is:";
	cout<<m[1][c]<<endl;


}