文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 回溯算法_01背包问题
侵权投诉

回溯算法_01背包问题

回溯算法_01背包问题

四、总结与讨论

通过这次试验,我掌握了回溯法的设计思想,如何构造解空间树,如何储存求解路径。

递归的思想:(1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。

(2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。

迭代的思想:对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。

附:程序模块的源代码

# include <stdio.h>

int c; //背包容量

int m; //物品数

int x[100];

int weight[100]; //物品重量

上一页第3页

你可能喜欢

  • 分支限界法
  • 算法设计与分析期末考试题
  • 问题解决
  • 动态问题
  • 新编大学英语4课文翻译
  • 最小生成树算法
  • 算法设计与分析王晓东
  • 页面置换算法

热门文档

相关文档

  • 回溯算法 01背包问题

    回溯算法 01背包问题_IT/计算机_专业资料。算法设计与分析淮海工学院计算机工程学院 实验报告书课 程名:题目: 《算法分析与设计》 实验 4 回溯算法 0/1 背包...

  • 01背包问题回溯算法

    01背包问题回溯算法_计算机软件及应用_IT/计算机_专业资料。假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能 被分割,且背包容量 M=150,使用...

  • 回溯法01背包问题

    回溯法01背包问题_计算机软件及应用_IT/计算机_专业资料。回溯法解决01背包问题 1、算法思想 2、问题描述 3、设计实现 回溯法01背包问题回溯法:是一个既带有...

  • 回溯法求01背包问题

    回溯法求01背包问题_IT/计算机_专业资料。实验题目 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值 为 vi,0/1 背包问题是如何选择装入...

  • 回溯算法之01背包问题java源程序

    回溯算法之01背包问题java源程序_计算机软件及应用_IT/计算机_专业资料。含背包类和物品类需要分文件实验报告 11 课程 数据结构与算法 实验名称 班级 11 计本 ...

  • 回溯法解决01背包问题

    回溯法解决01背包问题_互联网_IT/计算机_专业资料。回溯法解决01背包问题 回溯法解决01背包问题 1、算法思想 2、问题描述 3、设计实现 回溯法解决01背包问题回溯...

  • 实验五:01背包问题的回溯算法设计

    实验五:0/1 背包问题的回溯算法设计实验目的:0/1 背包问题的回溯算法设计 实验目的 实验原理:回溯算法设计。 实验原理 实验要求:基本掌握回溯算法设计的原理方法。...

  • 01背包问题的回溯法求解实验报告

    01背包问题的回溯法求解实验报告_IT/计算机_专业资料。01背包问题的回溯法求解实验报告,算法的一、实验目的(1) 理解回溯法的思想。 (2) 掌握一些经典的问题解决...

  • 蛮力法、动态规划法、回溯法和分支限界法求解01背包问题

    蛮力法、动态规划法、回溯法和分支限界法求解01背包问题_电脑基础知识_IT/计算机_专业资料。一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 ...

  • 回溯法01背包问题

    回溯法 背包问题 12页 1下载券喜欢此文档的还喜欢 回溯算法_01背包问题 7页...[100]; bag b; int n,i; cout<<"输入背包容量:"; cin>>b.w; cout<...

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