用贪心法求解背包问题的解决方法

贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。
应用：
1：该问题可以通过“局部寻优”逐步过渡到“整体最优”，这是贪心选择性质与“动态规划”的主要差别。
2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。
完整的代码如下：


代码如下:

#include "iostream"
using namespace std;
struct goodinfo
{
 float p; //物品效益
 float w; //物品重量
 float X; //物品该放的数量
 int flag; //物品编号
};//物品信息结构体
void Insertionsort(goodinfo goods[],int n)
{
 int j,i;
 for(j=2;j<=n;j++)
 {
  goods[0]=goods[j];
  i=j-1;
  while (goods[0].p>goods[i].p)
  {
   goods[i+1]=goods[i];
   i--;
  }
  goods[i+1]=goods[0];
 }
}//按物品效益，重量比值做升序排列
void bag(goodinfo goods[],float M,int n)
{
 float cu;
 int i,j;
 for(i=1;i<=n;i++)
  goods[i].X=0;
 cu=M;  //背包剩余容量
 for(i=1;i<n;i++)
 {
  if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
   break;
  goods[i].X=1;
  cu=cu-goods[i].w;//确定背包新的剩余容量
 }
 if(i<=n)
  goods[i].X=cu/goods[i].w;//该物品所要放的量
 //按物品编号做降序排列
 for(j=2;j<=n;j++)
 {
  goods[0]=goods[j];
  i=j-1;
  while (goods[0].flag<goods[i].flag)
  {
   goods[i+1]=goods[i];
   i--;
  }
  goods[i+1]=goods[0];
 }
 cout<<"最优解为:"<<endl;
 for(i=1;i<=n;i++)
 {
  cout<<"第"<<i<<"件物品要放:";
  cout<<goods[i].X<<endl;
 }
}
int main(void)
{
 cout<<"|--------运用贪心法解背包问题---------|"<<endl;
 cout<<"|-------------------------------------|"<<endl;
 int i,j,n;
 float M;
 goodinfo *goods;     //定义一个指针
 cout<<"press <1> to run the program"<<endl;
 cout<<"press <0> to exit"<<endl;
 cin>>j;
 while(j)
 {
  cout<<"请输入物品的总数量：";
  cin>>n;
  goods=new struct goodinfo [n+1];
  cout<<"请输入背包的最大容量：";
  cin>>M;
  cout<<endl;
  for(i=1;i<=n;i++)
  {
   goods[i].flag=i;
   cout<<"请输入第"<<i<<"件物品的重量:";
   cin>>goods[i].w;
   cout<<"请输入第"<<i<<"件物品的效益:";
   cin>>goods[i].p;
   goods[i].p=goods[i].p/goods[i].w;   //得出物品的效益，重量比
   cout<<endl;
  }
  Insertionsort(goods,n);
  bag(goods,M,n);
  cout<<"press <1> to run agian"<<endl;
  cout<<"press <0> to exit"<<endl;
  cin>>j;
 }
 system("pause");
 return 0;
}

赞 (0)

相关推荐

  • C#用递归算法解决经典背包问题

    1.引子 我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,用脑子才行,下面就教您如何解决这样的问题,以获得更多的奖品. 2.应用场景 在一个物品向量中找到一个子集满足条件如下 : 1)这个子集加起来的体积大小不能大于指定阀值 2)这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的 3.分析 背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个

  • C#使用回溯法解决背包问题实例分析

    本文实例讲述了C#使用回溯法解决背包问题的方法.分享给大家供大家参考.具体如下: 背包问题描述: 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高 实现代码: using System; using System.Collections.Generic; using System.Text; namespace BackRack { //要装入书包的货物节点 class BagNode { public int mark;//货物编号,从0开始

  • PHP动态规划解决0-1背包问题实例分析

    本文实例分析了PHP动态规划解决0-1背包问题.分享给大家供大家参考.具体分析如下: 背包问题描述:一个承受最大重量为W的背包,现在有n个物品,每个物品重量为t, 每个物品的价值为v. 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大. 思路:定义一个二维数组,一维为物品数量(表示每个物品),二维是重量(不超过最大,这里是15),下面数组a, 动态规划原理思想,max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值, opt(i-1,w-wi)指上一个最优解

  • C#使用动态规划解决0-1背包问题实例分析

    本文实例讲述了C#使用动态规划解决0-1背包问题的方法.分享给大家供大家参考.具体如下: // 利用动态规划解决0-1背包问题 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Knapsack_problem // 背包问题关键在于计算不超过背包的总容量的最大价值 { class Program { static void Main() { int i;

  • 关于背包问题的一些理解和应用

    关于背包问题的一些理解和应用

    1.背包问题介绍 背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下: 自从dd_engi在2007年推出<背包问题九讲>之后,背包问题的主要精髓基本已道尽.本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对<背包问题九讲>的理解)出发,帮助读者更快地学习<背包问题九讲>中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用. 2.

  • PHP回溯法解决0-1背包问题实例分析

    本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna

  • C++动态规划之背包问题解决方法

    本文实例讲述了C++动态规划之背包问题解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3   (W,N) 4 5   (w,p) 6 7   (w,p) 8 9   (w,p) 实现代码: #include <stdio.h> #define THING 20 #define WEIGHT 100 int arr[THING][WEIGHT]; /* 背包容量为wei

  • PHP贪婪算法解决0-1背包问题实例分析

    本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }

  • 用贪心法求解背包问题的解决方法

    贪心方法:总是对当前的问题作最好的选择,也就是局部寻优.最后得到整体最优.应用:1:该问题可以通过"局部寻优"逐步过渡到"整体最优",这是贪心选择性质与"动态规划"的主要差别.2:最优子结构性质:某个问题的整体最优解包含了"子"问题的最优解.完整的代码如下: 复制代码 代码如下: #include "iostream"using namespace std;struct goodinfo{ float p;

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • Python基于回溯法子集树模板解决0-1背包问题实例

    Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

  • php使用json_decode后数字对象转换成了科学计数法的解决方法

    本文实例讲述了php使用json_decode后数字对象转换成了科学计数法的解决方法.分享给大家供大家参考,具体如下: 问题: 今天在搞网页游戏在facebook积分上的对接,facebook传过来一个类json字符串,想在callball.php页面当中应用这些参数,于是进行了一次json_decode操作,发现长长的数字都变成了科学计数法,这不是我想要的结果. 解决方法: 做了各方面的转换处理都不好使: $obj='{"order_id":213477815351175,"

  • Javascript中toFixed计算错误(依赖银行家舍入法的缺陷)解决方法

    前言 在公司项目中涉及到一个有大量浮点数价格计算的模块,从而引发了我一系列的思考: 计算机二进制环境下浮点数的计算精度缺失问题; console.log(.1+.2); 0.30000000000000004 为了解决上述问题,使用了toFixed方法却出现了浮点数小数位以5结尾的四舍五入错误问题; var num = 0.045; console.log(num.toFixed(2)); 0.04 以此为起点,引发了我关于toFixed的一系列探索,终于找到了一些有用的信息,toFixed使用

  • C++超详细讲解贪心策略的设计及解决会场安排问题

    C++超详细讲解贪心策略的设计及解决会场安排问题

    目录 问题描述 贪心策略 算法设计 代码实现 选择结构体 随机输入会议 按结束时间排序 最终会议确定 结束语 问题描述 设有n个会议的集合C={1,2,…,n},其中每个会议都要求使用同一个资源(如会议室),而在同一时间内只能有一个会议使用该资源.每个会议i都有要求使用该资源的起始时间bi和结束时间ei,且bi < ei .如果选择了会议i使用会议室,则它在半开区间[bi, ei)内占用该资源.如果[bi, ei)与[bj , ej)不相交,则称会议i与会议j是相容的.会场安排问题要求在所给的会

  • SQL注入原理与解决方法代码示例

    一.什么是sql注入? 1.什么是sql注入呢? 所谓SQL注入,就是通过把SQL命令插入到Web表单递交或输入域名或页面请求的查询字符串,最终达到欺骗服务器执行恶意的SQL命令,比如先前的很多影视网站泄露VIP会员密码大多就是通过WEB表单递交查询字符暴出的,这类表单特别容易受到SQL注入式攻击．当应用程序使用输入内容来构造动态sql语句以访问数据库时,会发生sql注入攻击.如果代码使用存储过程,而这些存储过程作为包含未筛选的用户输入的字符串来传递,也会发生sql注入. 黑客通过SQL注入攻击

  • XP打印共享四大问题及解决方法

    XP打印共享四大问题及解决方法

    在Windows XP中,往往会因各种原因导致无法共享打印机,这个时候你是不是束手无策了?解决问题需要对症下药,让我们来了解一下在Windows XP中共享打印机时最容易出现的种种问题以及解决办法. 现象一:网上邻居无法正常浏览 在Windows XP中共享打印机,首先要做的并不是直接在工作站中安装网络打印机,而是应该先看看"网上邻居"中的"查看工作组计算机"项是否能正常浏览.是否出现安装有打印机的计算机(下称打印服务器).如果能够找到打印服务器,则表示共享打印机的

  • 无法显示隐藏文件夹（修改过注册表也无效）的解决方法 附注册表文件

    无法显示隐藏文件夹（修改过注册表也无效）的解决方法 附注册表文件

    显示隐藏文件的通法: 正常情况下,按照如下顺序操作即可:打开"我的电脑"的"工具"菜单--"文件夹选项",在"查看"标签里,选择"显示所有文件和文件夹",并找到"隐藏受保护的操作系统文件(推荐)",将前面的勾去掉.如下图所示: 被病毒修改注册表后导致无法显示隐藏文件的解决方法: 如果是由于病毒所导致的,则有很多种情况,这里说一下较常用的两种方法. 法一:打开注册表编辑器,进入注册表项:H

  • Realtek HD Audio Driver安装失败的解决方法

    主板是捷波主板P6AC-MX,芯片组是Intel945GC+ICH7,按照先主板驱动,后显卡,再声卡,结果却装来一个鸟"安装Realtek HD Audio Driver失败"的提示,晕.又听说是光盘里的驱动程序有问题,然后再到捷波的官方站下载驱动,再装,还是这个失败的提示.莫法,开动搜索思想,找来可行的解决方法. 先说下什么是HD Audio. HD Audio是High Definition Audio(高保真音频)的缩写,原称Azalia,是Intel与杜比(Dolby)公司合力

随机推荐