贪心算法 —— 背包问题
一、问题描述：有一堆宝物，用车去装载，一次运完（不能超过车的最大承重），要求运走价值高的宝物
这里因为物体是可分割的，所以我采用贪心算法。由题目可以得出，应该选取性价比最高的物品，即：价值/重量要最大才行。所以思路就出来了，每次选择性价比高的物品，如果其重量小于车的载重就装，如果大于就分割，部分装入。话不多说，直接上代码。
二、代码如下：
#include
#include
using namespace std;
const int M = 1000005;
struct three{
double weight;
double value;
double per; //性价比
}s[M];
bool compare(three a,three b){
return a.per>b.per; //定义从大到小排序
}
int main(void){
int n; //宝物总个数
double m; //最大载重量
cout<<"请输入宝物总个数和最大载重量："<>n>>m;
cout<<"请输入宝物的重量和价值:"<<endl;
for(int i=0; i>s[i].weight>>s[i].value;
s[i].per = s[i].value/s[i].weight;
}
sort(s,s+n,compare);
double sum = 0.0; //运走的宝贝
for(int i=0; is[i].weight){
m = m - s[i].weight;
sum = sum + s[i].value;
} else { // 部分装入
sum = sum + m*s[i].per;
break;
}
}
cout<<"可运走的宝物最大价值为："<<sum<<endl;
return 0;
}
时间复杂度为：O(nlogn)
作者：跨越七海的风丶
