阿里巴巴背包问题贪心算法
物品课分割的装载问题称为背包问题，物品不可分割的装载问题称为0-1背包问题。
#include
#include
using namespace std;
//按性价比贪心策略
typedef struct three {
double w; //重量
double v; //价值
double p; //性价比
three(double wi, double vi, double pi)
{
w = wi;
v = vi;
p = pi;
}
three()
{
}
}three;
bool cmp(three t1, three t2)
{
return t1.p > t2.p;
}
int main()
{
int m;//限制重量
int n; //货物种类
cout << "输入最多能装的重量以及货物的种类:" <> m >> n;
three* t = new three[n];//总共多少种货物
cout << "开始输入货物:" << endl;
for (int i = 0; i > t[i].w >> t[i].v;
t[i].p = t[i].v / t[i].w;
}
sort(t, t + n, cmp);
double sum=0,rev=m; //能装价值总和,剩余重量总和
for (int i = 0; i < n; i++)
{
cout << "货物：" << t[i].w <= t[i].w)
{
rev -= t[i].w;
sum += t[i].v;
}
else
{
sum += (t[i].p*rev);
break;
}
}
cout << "最多能得到价值为：" << sum << endl;
return 0;
}
作者：现实中我唯唯诺诺
