当前位置:首页 >> 工学 >>

回溯算法解决背包问题


template<class Typew, class Typep> class Knap//建立类 knap { friend Typew Knapsack(Typew* ,Typew*,Typew,int );//友元函数的声明 private://私有成员声明 Typew Bound(int i); void Backtrack(int i); Typew c;//背包容量 int n; //物品数 Typew *w;//物品重量数组 Typew *p;//物品价值数组 Typew cw;//当前重量 Typew cp;//当前价值 Typew bestp;//当前最优值 }; 第二段 template<class Typew, class Typep> void Knap<Typew, Typep>::Backtrack(int i)//友元函数的定义 { if(i>n){//到达叶结点 bestp=cp; return;} if(cw+w[i]<=c) //搜索左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp)//搜索右子树 Backtrack(i+1); }

1

第三段(重要)template<class Typew, class Typep> Typep Knap<Typew, Typep>::Bound(int i) {// 计算上界 Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } // 装满背包 if (i <= n) b += p[i]/w[i] * cleft; return b; } 第四段 class Object { friend int Knapsack(int *,int *,int ,int ); public: int operator<=(Object a)const { return (d>=a.d); } private: int ID;//对象好 float d;//收益密度 }; 第五段: template<class Typew, class Typep> Typew, Knapsack(tTypew,p[],Typew, w[],Typew,c,int n) { //为 Knap::Backtrack 初始化 Typew, W=0; Typew, P=0; Object *Q=new Object[n]; for(int i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i];}
2

if(W<=c) return P;//装入所有物品 //依物品单位重量排序 Sort(Q,n); Knap<Typew, Typep>K K.p = new Typep[n+1]; K.w = new Typep[n+1]; K.x = new Typep[n+1]; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; //回溯搜索 K.Backtrack(1); delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; } 补充 void main() { int *p; int *w; int c=0; int n=0; int i=0; cout<<"请输入背包个数:"<<endl; cin>>n; p=new int[n+1]; w=new int[n+1]; p[0]=0; w[0]=0;
3

cout<<"请输入背包容量:"<<endl; cin>>c; cout<<"请依此输入每个物品的重量:"<<endl; for(i=1;i<=n;i++) cin>>w[i]; cout<<"请依此输入每个物品的价值:"<<endl; for(i=1;i<=n;i++) cin>>p[i]; cout<<"所能装入背包中总价值最大为"<<Knapsack(p,w,c,n)<<endl; }

4


相关文章:
回溯算法解决0-1背包问题.doc
回溯算法解决0-1背包问题 - 《算法分析与设计》 实验报告 2015-2016
01背包问题回溯算法.doc
01背包问题回溯算法 - 假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能 被分割,且背包容量 M=150,使用回溯方法求解背包问题。请写 出状态...
用回溯法解决0-1背包问题.doc
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include<stdio.h> int c; //背包容量 ...
0-1背包问题的解决(回溯法).doc
回溯法| 背包| 0-1背包问题解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面...
回溯算法之01背包问题JAVA源程序.pdf
回溯算法之01背包问题JAVA源程序 - 实验报告 11 课程 数据结构与算法 班级 11 计本 实验名称 学号 回溯法 105032011130 第 姓名 页 风律澈 实验日期:2013 年....
回溯法解0-1背包问题实验报告.doc
实验4 一 、实验要求 回溯法解 0-1 背包问题 1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 ...
动态规划与回溯法解决0-1背包问题.doc
动态规划与回溯法解决0-1背包问题 - 0-1 背包动态规划解决问题 一、问题描
回溯法求0-1背包问题.doc
回溯法求0-1背包问题 - 《算法设计与分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
回溯算法解决0-1背包问题(DOC).doc
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015
回溯法01背包问题_图文.ppt
回溯法01背包问题 - 回溯法解决01背包问题 1、算法思想 2、问题描述 3、设计实现 回溯法01背包问题 回溯法:是一个既带有系统性又带有跳跃性的的 搜索算法。它...
回溯法和分支限界法解决0-1背包题.doc
回溯法解决 0-1 背包问题复杂度分析: 计算上界需要 O(n)时间, 在最坏情况下有 O(2^n)个右儿子节点需要计算上界, 故解 0-1 背包问题的回溯算法所需要的...
Pascal经典算法-背包问题析_图文.ppt
Pascal经典算法-背包问题析 - 经典算法问题解析---背包问题 前言 背包问题是程序设计中一个很经典的 问题,很多题目都是在该问题上延伸开来的, 对与背包问题我们...
动态规划解决算法0-1背包问题实验报告(含源代码).doc
动态规划解决算法0-1背包问题实验报告(含源代码) - 1.设计一个O(n^2)时间的算法,找出由n个数组成的序列的最长单调递增子序列 2.将算法分析题31中算法的...
回溯算法_01背包问题.doc
回溯算法_01背包问题 - 背包回溯算法 背包回溯算法 班级:10 级通信二班 学号:14102303001 姓名:蔡诚 成绩 分 一、设计目的 (1)掌握回溯法的设计思想; (2)...
算法分析与程序设计动态规划及回溯法解01背包问题.doc
算法分析与程序设计动态规划及回溯法解01背包问题 - 动态规划法、回溯法解 0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
01背包问题不同算法设计、分析与对比报告.doc
01背包问题不同算法设计、分析与对比报告 - 实验三 01 背包问题不同算法设计
回溯法实验(最优装载).doc
实验心得 在这一章的回溯算法中, 我们用的比较多的就是; 利用子集树来进行问题 的探索,就例如上图是典型的一种子集树,在最优装载、0-1 背包都是利用了 ...
算法分析复习题目及答案.doc
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1 背包问题 9. 实现循环赛日程表利用的算法是( a A、分治策略 B、动态规划法 )。 C、贪心法 D、回溯法 10...
算法分析复习题目及答案[1].doc
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1 背包问题 9. 实现循环赛日程表利用的算法是( A、分治策略 B、动态规划法 A )。 C、贪心法 D、回溯法 10...
回溯法在0_1背包问题中的应用.pdf
回溯法在0_1背包问题中的应用 - 第 7 卷 % 第 12 期 软件导刊 2008年 12 月 Software Guide Vol.7 No.12 Dec. 2008 回溯法...
更多相关标签: