knapsacktwoinone.cpp

0-1背包和 背包问题的动态规划 源程序 只是测试 不过要自己输入 还要自己加入 很简单就没有更改

#include <iostream>

using namespace std;

const int max=100000000u;


int c[20][1000];
int vpw[20]={0};

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

inline void Swap(int &x,int &y)
{
	int temp=x;
	x=y;
	y=temp;
}

void Sort(int *a,int *v,int *w,int n)
{
	//int temp;

	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(a[i]<a[j])
			{
				Swap(a[i],a[j]);
				Swap(v[i],v[j]);
				Swap(w[i],w[j]);
			}
}

void SortVPW(int *vpm,int *v,int *w,int n)//assume that v can be divided				
{				//exactly by w
	int i;
	for(i=0;i<=n;i++)
		vpw[i]=v[i]/w[i];
	Sort(vpw,v,w,n);
}

int Knapsack0_1(int *v,int *w,int n,int maxWeight)
{
	int i,j;

	for(i=0;i<=n;i++)
		c[i][0]=0;
	for(j=0;j<=maxWeight;j++)
		c[0][j]=0;

	for(i=1;i<=n;i++)
		for(j=1;j<=maxWeight;j++)
		{
			if(j-w[i]<0)
				continue;
			c[i][j]=Max(c[i-1][j-w[i]]+v[i],c[i-1][j]);
		}

	return c[n][maxWeight];
}	

float Knapsack(int *v,int *w,int n,int maxWeight)
{
	SortVPW(vpw,v,w,n);

	int weight=0;
	float value=0;
	int i=1;
	while(weight+w[i]<=maxWeight)
	{
		value+=v[i];
		weight+=w[i];
		i++;
	}
	if(weight!=maxWeight)
		value+=float(maxWeight-weight)/w[i]*v[i];
	return value;

}

int main()
{
	int v[]={0,200,180,225,200,50};
	int w[]={max,50,30,45,25,5};

	cout << Knapsack(v,w,5,100);
	return 0;
}