当前位置:首页 » 《休闲阅读》 » 正文

C语言背包问题求解(贪心方法)

11 人参与  2024年05月26日 10:48  分类 : 《休闲阅读》  评论

点击全文阅读


问题描述:

有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。物品:A    B    C    D    E    F    G重量:35  30   60  50   40  10  25价值:10  40   30  50   35  40  30

算法描述:

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
    贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

问题分析:

1.目标函数: ∑pi最大,使得装入背包中的所有物品pi的价值加起来最大。
2.约束条件:装入的物品总重量不超过背包容量:∑wi<=M( M=150)
3.贪心策略: 选择单位重量价值最大的物品

算法设计:

计算出每个物品单位重量的价值按单位价值从大到小将物品排序根据背包当前所剩容量选取物品如果背包的容量大于当前物品的重量,那么就将当前物品装进去。否则,那么就将当前物品分割再装进去,然后跳出循环结束。

代码实现:

#include<bits/stdc++.h>using namespace std;const int maxn = 1000;float z[maxn]; void Sort(int n,float w[],float v[]){for(int i=0;i<n;i++)z[i]=v[i]/w[i];//用z[]存物品的单位重量价值 for(int i=0;i<n;i++){//此排序的策略是每次把单位重量物品的价值最大的物品放在前面 for(int j=i+1;j<n;j++){if(z[i]<z[j]){float temp = z[i];z[i] = z[j];z[j]=temp;float tempw = w[i];w[i] = w[j];w[j] = tempw;float tempv = v[i];v[i] = v[j];v[j] = tempv; }}}} void fire(int n,float w[],float v[],float x[],float pimax){Sort(n,w,v);//根据单位重量物品的价值对物品进行排序 int i;for(i=0;i<n;i++){if(w[i]>pimax)break;x[i] = 1;//x[]数组用来记录此次是否选择物品,1代表全部拿走,0代表不拿,小数代表部分拿 pimax -= w[i];}if(i<=n-1)  x[i] = pimax/w[i]; }   int main(){int n;float pi=0; float pimax,v[maxn],w[maxn],x[maxn];//w[],每个物品的重量,v[]代表每个物品的价值,pimax代表最大容量 memset(x,0,sizeof(x));cout<<"请输入最大容量:";cin>>pimax;cout<<"请输入物品(物品可以任意分割)数量:";cin>>n;cout<<"请输入每个物品的重量和价值:"<<endl;for(int i=0;i<n;i++){cin>>w[i]>>v[i];}fire(n,w,v,x,pimax);for(int i=0;i<n;i++){if(x[i]==1){pi+=v[i];}else{pi+=v[i]*x[i];}}cout<<"最终收获的物品(物品可以任意分割)价值为:"<<pi<<endl;return 0;}

运行结果:


点击全文阅读


本文链接:http://zhangshiyu.com/post/113750.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 寒星碎梦不回舟(顾知舟安千雪)阅读 -
  • 穿越八零替嫁后我成了军官心尖宠完结版小说(杨念念陆时深)全文免费阅读无弹窗大结局_(穿越八零替嫁后我成了军官心尖宠完结版免费阅读全文大结局)最新章节列表_笔趣阁(穿越八零替嫁后我成了军官心尖宠完结版) -
  • 偏执占有完整版阅读沈黎月蒋美云(沈黎月蒋美云)全文免费阅读无弹窗大结局_(沈黎月蒋美云)偏执占有完整版阅读小说最新章节列表_笔趣阁(沈黎月蒋美云) -
  • 顾瑶陆泽免费阅读_顾瑶陆泽小说全文阅读笔趣阁
  • 《温玉溪陆霆琛》已完结小说全文阅读笔趣阁《温玉溪陆霆琛》
  • 最新好看小说推荐女朋友带全家白嫖我新年旅行(陈茜茜陈娇娇岩辉)_女朋友带全家白嫖我新年旅行(陈茜茜陈娇娇岩辉)完整版小说免费阅读
  • 和双胞胎姐姐互换身份后,老公悔疯了(林尔陈鸢)完本小说免费_全本免费小说和双胞胎姐姐互换身份后,老公悔疯了最新小说全文阅读(林尔陈鸢)
  • 最新热门小说斩断因果后,魔主跳出三界寻我_顾怜声林墨最热门小说_免费完结版小说(顾怜声林墨)
  • 春风有情难寻桃花(裴淮州沈轻语)免费阅读 -
  • 拨雪逢春,得见青山(江雨宁沈言澈)免费阅读 -
  • 我选光头大魔王很合理吧全章节(陈业唐紫尘)全文免费阅读无弹窗大结局_(陈业唐紫尘)我选光头大魔王很合理吧全章节小说最新章节列表_笔趣阁(我选光头大魔王很合理吧全章节) -
  • 《拼命挣钱给男友治病后,发现男友在装穷》无删减章节目录在线阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1