代做效果图网站哪家好,汉中市建设局网站,wordpress 清空 demo,简历设计网站贪心算法#xff0c;在对问题求解时#xff0c;总是做出在当前看来是最好的选择。也就是说#xff0c;不从整体最优上加以考虑#xff0c;算法得到的是在某种意义上的局部最优解 。
解题的一般步骤是#xff1a; 1.建立数学模型来描述问题#xff1b; 2.把求解的问题分成…贪心算法在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑算法得到的是在某种意义上的局部最优解 。
解题的一般步骤是 1.建立数学模型来描述问题 2.把求解的问题分成若干个子问题 3.对每一子问题求解得到子问题的局部最优解 4.把子问题的局部最优解合成原来问题的一个解。
在这里我们用贪心法来解决可切割物品的背包问题首先选择贪心属性比较所有物品的单价其次按照物品单价将所有物品从大到小进行排序最后优先把单价高的物品装进背包。将单价第一高的物品尽可能全部装入背包如果背包容量还有剩余则继续将单价第二高的物品尽可能装进背包…以此类推就可以求出背包问题的最优解。
在这个问题中可以使用结构体来储存物品及其价格与单价的信息在这里使用选择排序按照单价对结构体成员进行排序。
#includestdlib.h
#includetime.h
#includestdio.h
const int N10;
double value0;
struct goods{int No;//编号int w;//重量int v;//价值double avg;//单位重量的价值
};
void selectsort(goods g[]){//选择排序for(int i0;iN;i)for(int ji;jN;j)if(g[i].avgg[j].avg){goods x;xg[i];g[i]g[j];g[j]x;}
}
double greedy_tui(goods g[],int c)
{double value0;for(int i0;iN;i){//对排好序的物品按顺序进行贪心if(cg[i].w){if(c0){valuevaluec*g[i].avg;g[i].wg[i].w-c;c0;}else break;}else{valuevalueg[i].v;cc-g[i].w;}//Found!!!!!//先装哪个如何判断是否满了//什么时候需要分割物品如何记录最大价值 }return value;
}
int main()
{//srand((unsigned)time(NULL));int crand()%50;//初始化背包容量printf(背包最大承重:%d公斤\n,c);goods g[N]; for(int i0;iN;i)//初始化物品参数{g[i].Noi;g[i].wrand()%101;g[i].vrand()%101;g[i].avgg[i].v;g[i].avgg[i].avg/g[i].w;printf(物品%d重%d公斤,价值%d元\n,g[i].No,g[i].w,g[i].v);}selectsort(g);printf(排序后\n);for(int i0;iN;i) printf(物品%d重%d公斤,价值%d元\n,g[i].No,g[i].w,g[i].v);printf(递推能装入背包的最大价值为%f元\n,greedy_tui(g,c));return 0;
}
