贪心算法解决0-1背包问题(共6页).docx

精选优质文档-倾情为你奉上 贪心算法-0-1背包问题1、问题的描述有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,4,2,1,3，它们的价值分别是3,5,6,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？贪心算法的思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。2、代码及注释#include #define M 5/定义一个node结构体，用来存放物体的重量和价值struct node float value;/价值 float weight;/重量 int flag; /用来判别这个物体是否装进背包NodeM,temp;float Value,curvalue=0;/总价值和当前价值float Weight,curweight=0;/背包的最大承受重量和现有重量/按性价比