注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

【转载】贪心算法求解背包问题  

2017-07-07 22:52:59|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自流浪者《贪心算法求解背包问题》

一.需求分析

(1)       问题描述

已知有n种物品和一个可容纳M重量的背包,每种物品i的重量为W,假定将物

i的一部分Xi放人背包就会得到PiXi的效益,这里,oXi1Pi>0。采用怎

样的装包方法才会使装入背包物品的总效益最大

 

(2)       建立数学模型

极大化:(1)     贪心算法求解背包问题 - 流浪者 - 老栋的Blog

约束条件:(2)贪心算法求解背包问题 - 流浪者 - 老栋的Blog 

                            (3)贪心算法求解背包问题 - 流浪者 - 老栋的Blog
 


其中,(1)式是目标函数,(2)(3)是约束条件。满足约束条件的任一集合(x1…xn)

一个可行解(即能装下),使目标函数取最大值的可行解是最优解。

 

(3)   需要测试的数据

考虑下列背包问题:n=3M=20(p1p2p3)(252415) 

(w1,w2,w3)(181510)

 

二.概要设计

1) 主程序模块

void main(  )

{

输入数据;

判断检查;

贪心算法;

输出结果;

}

2  检查判断模块

   检查数据合法性,不能超过程序预定的最大值 total 。如果输入错误,请重新输

入,输入正确,往下执行

3  贪心算法设计

       采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准,这就需要使

物品的装入次序按pi/wi 比值的费增次序来考虑

 

Procedure GREEDY_KNAPSACK(P,W,M,X,n)

//P(1:n)W(1:n) 分别含有按P(i)/W(i)>=P(i+1)/W(i+1)排序的n件物品的效益//值和重量。M是背包的容量大小,而X(1:n)是解向量

real P(1:n),W(1:n),X(1:n),M,cu;

integer i,n;

X0     //将解向量初始化为0

cuM      //背包剩余容量

for i1 to n do

      if W(i)>cu then exit endif

      X(i)1

      cucu-W(i)

repeat

if i<=n then X(i) cu/W(i)

endif

end GREEDY_KNAPSACK

 

三.详细设计

 

(1)       数据类型的定义

//定义全局变量

#define total 10                      //物品的最大总数         

float p[total],w[total],t[total]; //p[]存储价值,w[]存储重量,t[]辅助数组

 

float cu;    //cu 保存当前背包容量

(2)       数据检查模块

       while(1)

       {

          scanf("%d%f",&n,&cu);

          if(n<total) break;

          else printf("物品总数超出范围,请重新输入:");

       }

(4)       数组的初始化

//t[i]辅助数组,用于标记第i件物品是否被贪心算法所采纳,1表采纳,0表否

    for(i=0;i<n;i++)

    {

       scanf("%f%f",&p[i],&w[i]);

       t[i]=0;               //初始化为0,表示未采纳

    }

(5)       贪心算法的详细设计

//形参,x表示物品数量,c表示当前背包剩余容量

void greedy_knaPsack(int x,int c)  

{

    int note,i;    //note 用于标记最大效益增速物品的下标

    float max;     //max存储最大效益增速值

    while(1)

    {

        note=0;

        max=0;

 

        for(i=0;i<x;i++)   //在所有物品里面选择效益增速最大的物品

           if((max<p[i]/w[i]) && (t[i]==0))

           {

               max=p[i]/w[i];

               note=i;

           }

 

        //如果该物品的重量<背包容量,则被贪心算法采纳,并将t[i]标记为1//表示已被采纳

        if(w[note]<c)   

        {

            t[note]=1;

            c-=w[note];

        }

        else   //如果该物品重量小于或者等于背包容量,则取部分

        {

            t[note]=c/w[note];

            break;           //退出循坏,表示贪心算法采纳结束

        }

    }

}

               

四.调试分析

1.只有一个核心算法,即贪心算法,背包问题,必须在某种度量标准下的最优解才具有意义,因此如何选择度量标准,成为解决该实际问题的关键

2.解决贪心算法问题的基本思路:

  1.建立数学模型来描述问题。

  2.把求解的问题分成若干个子问题。

  3.对每一子问题求解,得到子问题的局部最优解。

  4.把子问题的解局部最优解合成原来解问题的一个解。

  3. 贪心方法一般伴随着排序,当需要分析的数据量非常大的情况下,选择好的排序方式能大大有效提高程序的执行效率


五.用户手册

1)本程序的运行环境为DOS操作系统,执行文件为:main.exe

2)进入演示程序后,即显示文本方式的用户界面,用户只需要按提示输入:

     物品的总数与背包容量、物品的质量与效益

贪心算法求解背包问题 - 流浪者 - 老栋的Blog

六.测试结果

假设测试数据如下:

n=3M=20(p1p2p3)(252415)(w1,w2,w3)(181510)

 

     计算结果是:

贪心算法求解背包问题 - 流浪者 - 老栋的Blog
 

七.附录

  
 七.附录
源代码:
#include <stdio.h>
#define total 10
float p[total],w[total],t[total];

void greedy_knaPsack(int x,int c)
{
    int note,i;
    float max;
    while(1)
    {
        note=0;
        max=0;
        for(i=0;i<x;i++)
           if((max<p[i]/w[i]) && (t[i]==0))
           {
               max=p[i]/w[i];
               note=i;
           }
        if(w[note]<c)
        {
            t[note]=1;
            c-=w[note];
        }
        else
        {
            t[note]=c/w[note];
            break;
        }
    }
}

int main()
{
    int i=0,n=0;
    float cu;
    printf("请输入物品总数(不大于%d)与背包的容量:",total);
    while(1)
    {
        scanf("%d%f",&n,&cu);
        if(n<total) break;
        else printf("物品总数超出范围,请重新输入:");
    }
    printf("请输入每个物品的价值与重量:\n");
    for(i=0;i<n;i++)
    {
       scanf("%f%f",&p[i],&w[i]);
       t[i]=0;
    }
    greedy_knaPsack(n,cu);
    printf("由贪心算法所得最优解是:\n");
    for(i=0;i<n;i++)
        printf("%f   ",t[i]);
    return 0;
}

  




  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017