背包问题_贪心法
贪心法求解背包问题
【源程序】
//本程序的测试用例来源于课本例题 #include
#include
using namespace std;
struct G
{
double v;
double w;
double x=0;
int flag=0;
}good[100];
bool cmp1(G a, G b)//按照性价比降序排序 {
returna.v/a.w>b.v/b.w;
}
bool cmp2(G a, G b)//按照序号升序排序 {
returna.flag
}
int main()
{
inti, n, C;
doublemaxValue=0;
printf("请输入物品种类："); scanf("%d",&n);
printf("请输入背包重量："); scanf("%d",&C);
printf("请输入重量矩阵："); for(inti=0; i
{
scanf("%lf",&good[i].w); good[i].flag=i;
}
printf("请输入价值矩阵：");
for(inti=0; i
scanf("%lf",&good[i].v);
sort(good, good+n, cmp1);
for(i=0; good[i].w
{
good[i].x=1;
maxValue+=good[i].v;
C-=good[i].w;
}
good[i].x=(double)C/good[i].w;
maxValue+=good[i].x*good[i].v;
printf("背包的最大价值为:%.2f\n",maxValue);
sort(good, good+n, cmp2);
printf("问题的最优解向量为：");
for(inti=0; i
{
printf("%.1f ",good[i].x);
}
printf("\n");
return 0;
}
【运行结果】