文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 背包问题算法设计及分析
侵权投诉

背包问题算法设计及分析

背包问题

于淼:“背包问题”算法设计及分析

“背包问题”算法设计及分析

于

淼

(辽宁鞍山气象局

辽宁鞍山

114004)

摘要:“背包问题”是一个典型问题.其求解也是算法设计及验证的一个热点。在此分别采用优先策略、动态规划及递归三种不同方法对“背包问题”进行求解、算法设计及验证。实践证明了三种算法的正确性。在复杂度分析中,优先策略算法的空间及时间复杂度最低。而动态规划法具有明显的优势。

关键词:背包算法;优先策略;动态规划;栈操作

中图分类号:TP274

文献标识码:B

文章编号:1004—373X(2010)02一128一03

DesignandAnalysisofKnapsackProblem

YU

Miao

(AnshanMeteorologicalBureauofLiaoningProvince,Anshan.114004,China)

Abstract:Knapsackproblemistypicalproblemincomputerscienceanditssolutionis

a

hot

spot

inalgorithmsdesignand

verification.Thesolutionsfortheknapsackproblems,algorithmsdesignandverificationwiththreedifferentmeans:preferencestrategy,dynamicprogrammingandrecursion.Correctnessofthesethreealgorithmsare

proved,inthecomplexityanalysis,the

compiexityof

space

andtjmeinpreference

strategy

islowest,whilethedynamicprogramminghasobvioussuperiorjty.

Keywords:knapsackproblem;preferencestrategy;dynamicprogramming;stack

peration

0

引言

∑口m≤6,n。>o,f。>o,

I=1

算法研究是计算机科学的重要组成部分,有观点认z,一O或1,

1≤i≤卵

为“计算机科学是一门研究算法的科学”[1’2],无论这种2优先策略的算法设计

观点是否全面,都足以说明算法研究在计算机科学发展中所具有的重要作用及地位。算法研究是通过程序来按重量al≥以2≥倪3≥口。≥…≥口,,对z,进行调实践的。程序一算法+数据结构m”,这一大家都熟知整,作为待选队列。7’8I。

的公式更加表明算法研究不是单纯的数学问题,必须通假设前面已经选择了s个,即j¨j引…,歹。为最优过“实践”掌握算法的实质。这里对“背包问题”采用选择的前s件物品,则应满足:

优先策略、动态规划及递归三种不同方法进行求解、算%,fr。,…,f。,且∑口i<6

法设计及验证。并通过各种算法予以实现。本文研究、分析了实现“背包问题”算法的实质。

对后面等待选择的物品j。来说,与之对应的口。无疑满足:

1

问题描述

a女≤口i,

!一1,2,…,s

一旅行者携带背包去登山,已知所能随身携带的背

即所选择的物品重量比其所有待选择的物品重量大。

包重量限度为6,现有行种物品可供选择装入背包。

因此,对待选择的物品是否被选中将分为:∑盘。+

f=1

第i种物品重量为&,,其重要性价值指标为∞旅行者

应如何选择携带各种物品,以使总价值最大田^。

a。≤6和∑n。+以。>6两种情况。

£=1

“背包问题”的数学模型为:

(1)对于∑日。+口。≤6的情况,将z。插入已选择

max

2=∑啊。

f=1

的J队列中,然后根据c,的大小找到其相应的位置。

约束条件为:

(2)对于∑cz。+口。>6的情况,有:

f萱l

收稿日期:2009一09—16

①若存在靠≥c。,则将z。插入并按f。排序后,将

128

万方数据

第1页

你可能喜欢

  • 贪心算法
  • 背包问题课程设计
  • 农夫过河问题
  • 遗传算法
  • 最短路径算法
  • 数学建模
  • 动态规划算法

热门文档

相关文档

  • 算法设计与分析实验报告—01背包问题

    算法设计与分析实验报告—01背包问题_IT/计算机_专业资料。01背包问题算法设计与分析 实验报告—0/1 背包问题 - 【问题描述】 问题描述】给定 n 种物品和一个...

  • 背包问题_算法设计及分析

    “背包问题”算法设计及分析孙劲光辽宁工程技术大学电于与信息工程系.辽宁申新123000) 舟 要:髓肴刚,^技术的不断发展,阿络安全中有戈密码技术的应用作为有效口J...

  • _背包问题_算法设计及分析

    科学计算与信息处理 于 “背包问题” 淼: 算法设计及分析 “背包问题” 算法设计及分析于 淼 ( 辽宁鞍山气象局 辽宁 鞍山 114004) 摘 “背包问题” 要: 是...

  • 【论文】“背包问题”算法设计及分析

    “背包问题”算法设计及分析_专业资料。“背包问题”是一个典型问题.其求解也是算法设计及验证的一个热点。在此分别采用优先策略、动态规划及递归三种不同方法对“...

  • 动态规划法分析背包问题 算法设计

    动态规划法分析背包问题 算法设计_IT/计算机_专业资料。动态规划法分析背包问题 算法设计动态规划法分析背包问题 动态规划法分析背包问题马卫卫, 马卫卫, 09714026 ...

  • 0-1背包问题的算法设计策略对比与分析

    信息技术学院 算法设计与分析课程考查论文 题专班学姓任完 目 0-1 背包问题的算法设计策略对比与分析 业级号名课教师成日期 计算机科学与技术 *** *** 李** ...

  • 算法设计背包问题

    算法设计背包问题_数学_自然科学_专业资料。01背包,背包问题,算法设计背包问题,算法分析与设计-01背包问题算法实验报告 ---背包问题实验目的 1.掌握动态规划算法的...

  • 背包问题的算法设计与分析研究

    那么要解决背包问题, 首要的前提就是设计出好的算法, 想 求得背包问题的解, 就要先设计出算法。本文采用三种方法来对背包问题进行算法设计, 并分析其时间复杂度,...

  • 【论文】0-1背包问题的求解算法设计与分析

    0-1背包问题的求解算法设计与分析_专业资料。0-1背包问题在信息密码学和数论研究中有着极其重要的应用。首先对背包问题作了简要描述,然后对0-1背包问题的两种...

  • 算法分析与设计背包问题实验报告

    算法设计与分析 实验报告 ---背包问题 实验名称:算法分析与设计—01 背包问题 院系名称:计算机学院 专班学业:软件工程 级: 号: 学生姓名:李书伟 指导教师:强赞...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email