我要评论问题描述：
1.设有一个载重量为10的背包，现有4个可拆分物品，每个物品的重量分别为(w1,w2,w3,w4)=(2,4,5,6)，它们的价值分别为(p1,p2,p3,p4)=(2,3,5,8)。试问：如何装载才能使得装入背包中的物品的总价值最大?
(1)请设计并实现一个求解该问题的贪心算法，指出所采用的贪心选择策略。
(2)求出最大收益，以及具体的装载方案。
贪心选择策略：优先依次选择性价比最高，即单位 价值/重量 的值最大的物品，若物品不能整个放下就进行相应的分割，以此装载的获得的物品总价值最大；
参考代码如下：
#include<iostream>
using namespace std;
int n = 4, m= 10;
int w[] ={2,4,5,6};
int p[]= {2,3,5,8};
struct hh{
int wei, value;
double performance;
bool operator<(const hh& x)const{
return performance >x.performance;
}
}a[10];
int main(){
for(int i = 0;i<n; ++i){
a[i].wei =w[i];
a[i].value = p[i];
a[i].performance =1.0*p[i]/w[i];
}
sort(a,a+n);
for(int i=0;i<n;++i){
printf("w.%d value:%d performance:%.21f\n",a[i].value,a[i].performance);
}
dobule val = 0;
for(int i= ;i<n;++i){
// 如果能放下整个物品
if(a[i].wei<= m){
m -=a[i].wei;
val +=a[i].value;
}
else //分割物品
{
val +=a[i].performance *m;
m -=m;
break; // 省去后面无用的循环
}
}
printf("最大总价值 = %。21f\n", val);
return 0;
(2）最大收益是选择第四件，第一件整个物品以及两个重量单位的第三件物品，总价值为12.
发表评论