exp4.cpp

部分背包问题（不同于0-1背包） C++实现

#include<iostream>
using namespace std;
const int maxi=100;
int n;
float x[maxi],c;
struct value
{
	float v,w,d;
	int s;
}val[maxi];
void knapsack(value val[],float x[])
{
	int i,j;
	for(i=0;i<n;i++)
	{
		val[i].s=i;
		val[i].d=val[i].v/val[i].w;
	}
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++)
			if(val[i].d<val[j].d)
			{
				value temp=val[i];
				val[i]=val[j];
				val[j]=temp;
			}
	float opt=0;
	for(i=0;i<n;i++)
		x[i]=0;
	i=0;
	while((i<n-1)&&(val[i].w<=c))
	{
		x[i]=1;
		c-=val[i].w;
		opt+=val[i].v;
		i++;
	}
	if(i<n-1)
	{
		x[i]=c/val[i].w;
		opt+=x[i]*val[i].v;
	}
	cout<<"背包依次装入物品的体积为："<<endl;
	for(i=0;i<n;i++)
	{
		cout<<"    x["<<val[i].s<<']';
	}
	cout<<endl<<'(';
	for(i=0;i<n;i++)
		cout<<"    "<<x[i];
	cout<<" )"<<endl;
    cout<<"背包所能装的物品的总价值为："<<opt<<endl;
}
int main()
{
	cout<<"请输入背包体积:：c=";
	cin>>c;
	cout<<"请输入物品总数：n=";
	cin>>n;
	int i;
	cout<<"请依次输入每件物品的价值："<<endl;
	for(i=0;i<n;i++)
		cin>>val[i].v;
	cout<<"请依次输入每件物品的体积："<<endl;
	for(i=0;i<n;i++)
		cin>>val[i].w;
	knapsack(val,x);
	return 0;
}