背包问题
题目：已知一个容量大小为 m 重量的背包和 n 种物品，每种物品 i 的重量为 w[i],如果将物品i的一部分x[i]（x[i]在0和1之间）放到背包就会得到p[i]*x[i]（p[i]>0）的效益请问怎样包装可以得到最大效益？输出该最大效益
m=25
n=6
w[]={8,15,10,12,6,25}
p[]={25,24,15,20,30,12}
求代码和解释
2012-04-10 15:40
2012-04-10 23:51
2012-04-13 11:40
程序代码：
#include <iostream>
using namespace std;
int main()
{ float m=25;
float w[]={8,15,10,12,6,25};
float p[]={25,24,15,20,30,12};
float per[6];
int i,j,t;
for(i=0;i<6;i++)
{
per[i]=p[i]/w[i];
}
for(i=0;i<5;i++)
{
for(j=0;i<6-j-1;j++)
{
if(per[j]>per[j+1])
{
t=per[j];
per[j]=per[j+1];
per[j+1]=t;
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
}
}
}
//
float _w=0;
float _p=0;
for(i=0;i<6;i++)
{
if(_w+w[i]<m)
{
_w+=w[i];
_p+=p[i];
}
else
{
_p=((m-_w)/w[i])*p[i];
break;
}
}
cout<<_p<<endl;
return 1;
}
2012-04-15 00:16
2012-04-15 00:17
2012-04-15 00:18