您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > C/C++/C#

C++编程笔记:贪心算法实现部分背包问题

时间:2019-11-07 10:44:12  来源:  作者:

C++编程笔记:贪心算法实现部分背包问题

 

问题描述:

在部分背包问题中,可以不必拿走整个一件物品,而是可以拿走该物品的任意部分。以此求得在限定背包总重量,从给定的物品中进行选择的情况下的最佳(总价值最高)的选择方案。

细节须知:

分别输出到同文件夹下两个文本文件中,名称分别是:“backpack-object.txt”和“backpack-weight.txt”。

算法原理:

先求出所有物品的单位重量价值并进行由大到小的排序。其次从排序处于首位的物品开始选择直到无法完整装入背包的物品,将其部分装入背包以填满背包的总重量,从而求得价值最高的选择方案。

C++编程笔记:贪心算法实现部分背包问题

 

 

C++编程笔记:贪心算法实现部分背包问题

 

 

C++编程笔记:贪心算法实现部分背包问题

 

程序设计思路:

① 数据结构:结构体中存储物品序号、物品的重量、物品的价值、物品的单位重量价值;

② 利用C++自带的sort函数对结构体按照物品的单位重量价值进行降序排列;

③ 从排序处于首位的物品开始选择直到无法完整装入背包的物品,将其部分装入背包以填满背包的总重量,从而求得价值最高的选择方案。

时间复杂性分析:

首先,需要对输入的物品单位重量价值进行非减序排序,需要用O(nlogn)的时间。其次,当输入的物品已按物品单位重量价值非减序排列,算法只需θ(n)的时间选择n个物品,使算法可以求得价值最高的选择方案。

生成的数据可导入Excel中进行数据分析生成分析图表。

博客园:Weisswire

想要在程序员生涯内有更高的成就的话,C/C++就是一个既可以强化思维能力,又可以打好编程基础的编程语言,你想要做软件开发,成为核心程序员的话,学习C/C++的话笔者有一个C/C++的编程千人羣(Q艘索:C语言编程学习聚集地(无言建立))你如果感觉自学C/C++语言有困难的话,有兴趣学习或者了解一下C/C++编程的小伙伴就可以进来交流。

C++编程笔记:贪心算法实现部分背包问题

 



Tags:C++   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一、编程语言1.根据熟悉的语言,谈谈两种语言的区别?主要浅谈下C/C++和PHP语言的区别:1)PHP弱类型语言,一种脚本语言,对数据的类型不要求过多,较多的应用于Web应用开发,现在好多互...【详细内容】
2021-12-15  Tags: C++  点击:(17)  评论:(0)  加入收藏
函数调用约定(Calling Convention),是一个重要的基础概念,用来规定调用者和被调用者是如何传递参数的,既调用者如何将参数按照什么样的规范传递给被调用者。在参数传递中,有两个很...【详细内容】
2021-11-30  Tags: C++  点击:(19)  评论:(0)  加入收藏
一、为什么需要使用内存池在C/C++中我们通常使用malloc,free或new,delete来动态分配内存。一方面,因为这些函数涉及到了系统调用,所以频繁的调用必然会导致程序性能的损耗;另一...【详细内容】
2021-11-17  Tags: C++  点击:(38)  评论:(0)  加入收藏
C++编程中,你是否有为 我到底该写个struct还是class 而苦恼过?如果你到现在还不知道该如何选择,那么请求继续阅读,下文或许能给你些建议。问题的产生C++语言继承了 C语言的 stru...【详细内容】
2021-10-18  Tags: C++  点击:(63)  评论:(0)  加入收藏
C++在C的面向过程概念的基础上提供了面向对象和模板(泛型编程)的语法功能。下面以一个简单实例(动态数组的简单封装,包括下标的值可以是任意正数值,并提供边界检查)来说明C++是如...【详细内容】
2021-10-18  Tags: C++  点击:(50)  评论:(0)  加入收藏
0 前言Hello,大家好,欢迎来到『自由技艺』的 C++ 系列专题。代码重用,尽可能避免冗余代码是程序员的一项必备技能,今天就来给大家介绍其中一种:函数装饰器。在设计模式中,与它对应...【详细内容】
2021-09-28  Tags: C++  点击:(75)  评论:(0)  加入收藏
今天我们就来聊一聊 C++ 中的异常机制吧。在学校期间,我们很少会用得上异常机制。然而,工作之后,很多时候却不得不引入异常机制。因为一般情况下,使用函数的返回值来确定函数的...【详细内容】
2021-09-26  Tags: C++  点击:(182)  评论:(0)  加入收藏
一、内存泄漏(memory leak)内存泄漏(memory leak)是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。内存泄漏并非指内存在物理上的消失,而是应用程序分配某段内存...【详细内容】
2021-09-03  Tags: C++  点击:(105)  评论:(0)  加入收藏
stack容器#include <iostream>using namespace std;#include <stack>//容器头文件void test(){stack<int>p;p.push(100);p.push(1000);p.push(100);while(!p.empty()){cout<...【详细内容】
2021-08-17  Tags: C++  点击:(81)  评论:(0)  加入收藏
stl 常用遍历算法(for_each transform)示例代码(结论在结尾!!!!)#include<iostream>using namespace std;#include"vector"#include"map"#include"string"#include"list"#in...【详细内容】
2021-08-13  Tags: C++  点击:(89)  评论:(0)  加入收藏
▌简易百科推荐
一、简介很多时候我们都需要用到一些验证的方法,有时候需要用正则表达式校验数据时,往往需要到网上找很久,结果找到的还不是很符合自己想要的。所以我把自己整理的校验帮助类分...【详细内容】
2021-12-27  中年农码工    Tags:C#   点击:(2)  评论:(0)  加入收藏
引言在学习C语言或者其他编程语言的时候,我们编写的一个程序代码,基本都是在屏幕上打印出 hello world ,开始步入编程世(深)界(坑)的。C 语言版本的 hello world 代码:#include <std...【详细内容】
2021-12-21  一起学嵌入式    Tags:C 语言   点击:(11)  评论:(0)  加入收藏
读取SQLite数据库,就是读取一个路径\\192.168.100.**\position\db.sqlite下的文件<startup useLegacyV2RuntimeActivationPolicy="true"> <supportedRuntime version="v4.0"/...【详细内容】
2021-12-16  今朝我的奋斗    Tags:c#   点击:(21)  评论:(0)  加入收藏
什么是shellshell是c语言编写的程序,它在用户和操作系统之间架起了一座桥梁,用户可以通过这个桥梁访问操作系统内核服务。 它既是一种命令语言,同时也是一种程序设计语言,你可以...【详细内容】
2021-12-16  梦回故里归来    Tags:shell脚本   点击:(18)  评论:(0)  加入收藏
一、编程语言1.根据熟悉的语言,谈谈两种语言的区别?主要浅谈下C/C++和PHP语言的区别:1)PHP弱类型语言,一种脚本语言,对数据的类型不要求过多,较多的应用于Web应用开发,现在好多互...【详细内容】
2021-12-15  linux上的码农    Tags:c/c++   点击:(17)  评论:(0)  加入收藏
1.字符串数组+初始化char s1[]="array"; //字符数组char s2[6]="array"; //数组长度=字符串长度+1,因为字符串末尾会自动添&lsquo;\0&lsquo;printf("%s,%c\n",s1,s2[2]);...【详细内容】
2021-12-08  灯-灯灯    Tags:C语言   点击:(47)  评论:(0)  加入收藏
函数调用约定(Calling Convention),是一个重要的基础概念,用来规定调用者和被调用者是如何传递参数的,既调用者如何将参数按照什么样的规范传递给被调用者。在参数传递中,有两个很...【详细内容】
2021-11-30  小智雅汇    Tags:函数   点击:(19)  评论:(0)  加入收藏
一、问题提出问题:把m个苹果放入n个盘子中,允许有的盘子为空,共有多少种方法?注:5,1,1和1 5 1属同一种方法m,n均小于10二、算法分析设f(m,n) 为m个苹果,n个盘子的放法数目,则先对...【详细内容】
2021-11-17  C语言编程    Tags:C语言   点击:(49)  评论:(0)  加入收藏
一、为什么需要使用内存池在C/C++中我们通常使用malloc,free或new,delete来动态分配内存。一方面,因为这些函数涉及到了系统调用,所以频繁的调用必然会导致程序性能的损耗;另一...【详细内容】
2021-11-17  深度Linux    Tags:C++   点击:(38)  评论:(0)  加入收藏
OpenCV(Open Source Computer Vision Library)是一个(开源免费)发行的跨平台计算机视觉库,可以运行在Linux、Windows、Android、ios等操作系统上,它轻量级而且高效---由一系列...【详细内容】
2021-11-11  zls315    Tags:C#   点击:(50)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条