当前位置:首页 >> 幼儿读物 >>

01背包问题不同算法设计、分析与对比报告


实验三 01 背包问题不同算法设计、分析与对比
一.问题描述
给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为 vi,背包的容量为 c。 问题:应如何选择装入背包中的物品,使得装入背包中物品的总价值最大。 说明:在选择装入背包的物品时,对每种物品 i 只有两个选择,装入背包或 不装入背包,也不能将物品装入背包多次。

二.实验内容与要求
实验内容: 1.分析该问题适合采用哪些算法求解(包括近似解)。 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计,并进行算法复杂性分 析。 动态规划: 递推方程: m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为 O(n). 贪心法: 算法思想:贪心原则为单位价值最大且重量最小,不超过背包最大承重量 为约束条件。也就是说,存在单位重量价值相等的两个包,则选取重量较小的那 个背包。但是,贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪 心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考 虑,它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特点是一步一步地进行,根据某个优化测度(可能是目 标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步 只考虑一个数据, 它的选取应满足局部优化条件。若下一个数据与部分最优解连 在一起不再是可行解时,就不把该数据添加到部分解中, 直到把所有数据枚举完,或者不能再添加为止。 回溯法: 回溯法: 为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限 界函数(bounding function)来处死那些实际上不可能产生所需解的活结点, 以 减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。

对于有 n 种可选物品的 0/1 背包问题,其解空间由长度为 n 的 0-1 向量组成, 可用子集数表示。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索 就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为:O(2n) 空间复杂度为:O(n) 分支限界算法: 首先, 要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行 排列。 在优先队列分支限界法中,节点的优先级由已装袋的物品价值加上剩下的 最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。 如果该左儿子结点是可 行结点, 则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点 一定是可行结点, 仅当右儿子结点满足上界约束时才将它加入子集树和活结点优 先队列。当扩展到叶节点时为问题的最优值。 3.设计并实现所设计的算法。 4.对比不同算法求解该问题的优劣。 这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的, 当一件 背包物品可以分割的时候,使用贪心算法,按物品的单位体积的价值排序,从大 到小取即可。 当一件背包物品不可分割的时候,(因为不可分割,所以就算按 物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的,应 使用动态规划。 设计方法 动态规划 时间复杂度 Min{nc,2n} 优点 缺点

可 求 得 最 优 决 策 速度慢 序列

贪心方法 回溯法 分支限界法

O(2n) O(n2n) O(2n)

速度较快 能够得到最优解

很难得到最优解 时间复杂度较高

速度较快,易求解 占用内存大,效率 不高

5.需要提交不同算法的实现代码和总结报告。 动态规划方法:
public class Knapsack { public static void main(String[] args) { int[] value = { 0, 60, 100, 120 }; int[] weigh = { 0, 10, 20, 30 }; int weight = 50; Knapsack1(weight, value, weigh);

} public static void Knapsack1(int weight, int[] value, int[] weigh) { int[] v = new int[value.length]; int[] w = new int[weigh.length]; int[][] c = new int[value.length][weight + 1]; int d[] = new int [100]; for (int i = 0; i < value.length; i++) { v[i] = value[i]; w[i] = weigh[i]; } for (int i = 1; i < value.length; i++) { for (int k = 1; k <= weight; k++) { if (w[i] <= k) { c[i][k] = max(c[i - 1][k], c[i - 1][k - w[i]] + v[i]); } else { c[i][k] = c[i - 1][k]; } } } System.out.println(c[value.length - 1][weight]); } private static int max(int i, int j) { int k = i > j ? i : j; return k; } }

贪心法:
public class GreedyKnapSack { public static void main(String[] args) { int[] value = { 0, 60, 100, 120 }; int[] weigh = { 0, 10, 20, 30 }; int weight = 50; Knapsack1(weight, value, weigh); } private static void Knapsack1(int weight, int[] v, int[] w) { int n = v.length; double[] r = new double[n]; int[] index = new int[n]; for(int i = 0;i < n; i++) { r[i] = (double)v[i] / (double)w[i];

index[i] = i; } //按单位重量价值 r[i]=v[i]/w[i]降序排列 double temp = 0; for(int i = 0;i < n-1;i++){ for(int j = i+1;j < n;j++){ if(r[i] < r[j]){ temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } //排序后的重量和价值分别存到 w1[]和 v1[]中 int[] w1 = new int[n]; int[] v1 = new int[n]; for(int i = 0;i < n;i++){ w1[i] = w[index[i]]; v1[i] = v[index[i]]; } System.out.println (Arrays.toString(w1)); System.out.println (Arrays.toString(v1)); int s=0;//包内现存货品的重量 int value=0;//包内现存货品总价值 for(int i = 0; i < n;i++){ if(s + w1[i] < weight){ value += v1[i]; s += w1[i]; } } System.out.println("背包中物品的最大总价值为" + value); } }

回溯法:
public class BacktrackKnapSack { public static void main(String[] args) { int[] value = { 0, 60, 100, 120 }; int[] weigh = { 0, 10, 20, 30 }; int weight = 50; Knapsack1(weight, value, weigh); }

private static void Knapsack1(int weight, int[] v, int[] w) { int n = v.length; double[] r = new double[n]; int[] index = new int[n]; for(int i = 0;i < n; i++) index[i] = i; } //按单位重量价值 r[i]=v[i]/w[i]降序排列 double temp = 0; for(int i = 0;i < n-1;i++){ for(int j = i+1;j < n;j++){ if(r[i] < r[j]){ temp = r[i]; r[i] = r[j]; r[j] = temp; int x = index[i]; index[i] = index[j]; index[j] = x; } } } //排序后的重量和价值分别存到 w1[]和 v1[]中 int[] w1 = new int[n]; int[] v1 = new int[n]; for(int i = 0;i < n;i++){ w1[i] = w[index[i]]; v1[i] = v[index[i]]; } //调用函数 KnapSackBackTrack(),输出打印装完物品以后的最大价值 KnapSackBackTrack(w1,v1,w1.length,weight); } private static void KnapSackBackTrack(int[] w1, int[] v1, int length, int weight) { int CurrentWeight = 0; int CurrentValue = 0; int maxValue = 0; int i = 0; int n = v1.length; while(i >= 0){ if(CurrentWeight + w1[i] < weight){ CurrentWeight += w1[i]; { r[i] = (double)v[i] / (double)w[i];

CurrentValue += v1[i]; i++; } else break; } if(i < n){ maxValue = CurrentValue; System.out.println("1 背包中物品的最大总价值为" + maxValue); } } }

分支限界算法:
package bag01b; import java.util.ArrayList;
public class bag01do { public static void main(String[] args) { // TODO Auto-generated method stub ArrayList<object> objects=new ArrayList<>(); objects.add(new object(10,60)); objects.add(new object(20,100)); objects.add(new object(30,120)); bag b=new bag(50,objects); b.findmaxvalue(); b.show(); } }

----------------------------------------------------------------------package bag01b; import java.util.ArrayList; import java.util.Collections; import java.util.PriorityQueue; public class private private private private bag { int bagv; ArrayList<object> objects; int maxvalue; ArrayList<object> result_objects;

public bag(int v,ArrayList<object> o){

super(); this.bagv=v; this.objects=o; this.maxvalue=0; this.result_objects=null; Collections.sort(objects); } public void show(){ System.out.println("maxvalue :"+ this.maxvalue); System.out.println("the object maxvalue:"+this.result_objects); }

when

public void findmaxvalue(){ PriorityQueue<Node> enode=new PriorityQueue<>(); Node node=new Node(0,null,bagv,this.objects); enode.offer(node); while(true){ if(enode.isEmpty()) break; node=enode.poll(); if(node.isend()){ this.maxvalue=node.get_bag_value(); this.result_objects=new ArrayList<>(node.get_in_bag_object()); return; } int i=node.get_node_in(); object iobject=this.objects.get(i); if(node.get_bag_weight()+iobject.getweight()<=this.bagv){ ArrayList<object> newnodeinbag=new ArrayList<object>(node.get_in_bag_object()); newnodeinbag.add(iobject); int newnodebagv=node.get_bag_leftv()-iobject.getweight(); Node newnode=new Node(i+1,newnodeinbag,newnodebagv,this.objects); enode.add(newnode); if(newnode.get_bag_value()>this.maxvalue){ this.maxvalue=newnode.get_bag_value(); this.result_objects=new ArrayList<>(newnode.get_in_bag_object()); } }

Node newnode=new Node(i+1,node.get_in_bag_object(),node.get_bag_leftv(),this.objects); if(newnode.get_bag_prio()>this.maxvalue) enode.add(newnode); } } } ----------------------------------------------------------------------package bag01b; import java.util.ArrayList; public class Node implements Comparable<Node>{ private int node_in; private ArrayList<object> inbag_object; private ArrayList<object> outbag_object; private int leftv; private int prio; public Node(int i,ArrayList<object> in,int l,ArrayList<object> out){ super(); this.node_in=i; if(in==null) in=new ArrayList<>(); this.inbag_object=in; this.leftv=l; this.outbag_object=out; this.prio=this.find_prio(); } private int find_prio() { // TODO Auto-generated method stub int bag_left=this.leftv; int p=this.get_bag_value(); int i=this.node_in; object iobject=null; while(true){ if(i>=this.inbag_object.size()) break; iobject=this.inbag_object.get(i); if(iobject.getweight()>bag_left) break; bag_left-=iobject.getweight(); p+=iobject.getvalue();

i++; } if(i<=this.inbag_object.size()-1) p+=iobject.getvw()*bag_left; return p; } public int get_bag_weight(){ int w=0; for(object o:this.inbag_object){ w+=o.getweight(); } return w; } public int get_bag_value(){ int w=0; for(object o:this.inbag_object){ w+=o.getvalue(); } return w; } @Override public int compareTo(Node o) { // TODO Auto-generated method stub if(this.prio>o.prio) return -1; if(this.prio<o.prio) return 1; return 0; } public boolean isend(){ if(this.node_in==this.outbag_object.size()) return true; else return false; } public ArrayList<object> get_in_bag_object(){ return this.inbag_object; } public int get_node_in(){return this.node_in;} public int get_bag_leftv(){return this.leftv;} public int get_bag_prio(){return this.prio;} public String toString(){ return "node in"+this.node_in+"node prio"+this.prio; } } -----------------------------------------------------------------------

package bag01b; public class object implements Comparable<object>{ private static int ids=1; private int id; private int weihgt; private int value; public object(int w,int v){ super(); this.weihgt=w; this.value=v; this.id=ids++; } public int getid(){return this.id;} public int getweight(){return this.weihgt;} public int getvalue(){return this.value;} public float getvw(){return (float)this.value/this.weihgt;} @Override public int compareTo(object o) { // TODO Auto-generated method stub if(this.getvw()>o.getvw()) return -1; if(this.getvw()<o.getvw()) return 1; return 0; } public String toString(){ return "object "+this.id+" } }

";


相关文章:
01背包问题不同算法设计、分析与对比报告.doc
01背包问题不同算法设计分析与对比报告 - 实验三 01 背包问题不同算法设计、分析与对比 一.问题描述 给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为...
01背包问题不同算法设计、分析与对比.doc
01背包问题不同算法设计分析与对比 - 实践动态规划、贪心、回溯以及分支限界算
0-1背包问题的算法设计策略对比与分析报告.doc
0-1背包问题算法设计策略对比与分析报告 - 算法设计与分析大作业 班姓学 级
01背包问题不同算法设计、与对比讲解.doc
01背包问题不同算法设计、与对比讲解 - 实验三 01 背包问题不同算法设计分析与对比 一.问题描述 给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为 vi...
(华电科院)算法设计与分析实验报告01背包问题.doc
(华电科院)算法设计与分析实验报告01背包问题 - 课程设计报告 ( 2013 -- 2014 年度第 一 学期) 名题院班学 称: 算法设计与分析 目系: 级: 号: 01...
算法设计与分析--01背包问题(动态规划法解决)_图文.pdf
算法设计与分析--01背包问题(动态规划法解决)_电子/电路_工程科技_专业资料。 ...01背包动态规划法 3页 免费 算法设计与分析实验报告... 6页 5下载券 动...
算法设计-01背包问题的分析.doc
算法设计-01背包问题分析_工学_高等教育_教育专区。个人对于01背包问题的一个简单认识 算法设计与分析 ---0/1 背包问题实例研究 班级:090402 学号:20091236...
算法分析与设计论文-背包问题的算法设计策略对比与分析.doc
算法分析与设计论文-背包问题的算法设计策略对比与分析 - 算法设计与分析论文 题专班学姓 目 0-1 背包问题算法设计策略对比与分析 业级号名 引言 对于计算机...
算法设计与分析实验报告01背包问题.doc
算法设计与分析实验报告01背包问题 - 算法设计与分析 实验报告 0/1 背包问题 - 【问题描述】 问题描述】 给定 n 种物品一个背包。 种物品一个背包。...
算法分析与设计背包问题的算法设计策略对比与分析大学论文.doc
算法分析与设计背包问题的算法设计策略对比与分析大学论文 - 算法设计与分析论文 题专班学姓 目 0-1 背包问题算法设计策略对比与分析 业级号名 引言 对于...
0-1背包问题的算法设计策略对比与讲解.doc
0-1背包问题算法设计策略对比与讲解 - 算法设计与分析大作业 班姓学 级:
背包问题_算法设计及分析_图文.pdf
背包问题_算法设计及分析 第2l卷、,01.2l, 第2...在选择队列 最好情况下的运算次数为n.1比较运算和...算法设计与分析实验报告... 6页 5下载券 算法...
算法分析与设计实验报告之01背包问题.doc
算法分析与设计实验报告01背包问题 - 算法分析与设计实验报告 [0/1 背包问题 背包问题] 0/1 背包问题的不同算法解决方案 组员 0945532112 黄希龙 09455321 张...
01背包 算法设计课程实验报告.doc
01背包 算法设计课程实验报告 - 算法设计分析课程 设计 题目 0-1 背包 班级: 组号: 姓名: 一,0-1 背包问题描述: 给定 n 种物品和一背包。物品 ...
算法分析与设计背包问题实验报告.doc
算法设计与分析 实验报告 ---背包问题 实验名称:算法分析与设计01 背包问题 院系名称:计算机学院 专班学业:软件工程 级: 号: 学生姓名:李书伟 指导教师:强赞...
01背包问题题解.doc
费用价值均不变的物品,然后求解这个 01 背包问题...0-1背包问题解题报告 3页 免费 0_1背包问题的多...算法设计与分析实验报告... 6页 5下载券 ...
北邮 算法设计与分析_第三章实验报告.doc
北邮 算法设计与分析_第三章实验报告_工学_高等教育_教育专区。算法设计与分析...01 背包问题 #include<stdio.h> #include<stdlib.h> #define N 100 struct ...
算法实验报告01背包问题.doc
算法实验报告01背包问题 - hebut的,你懂得。动态规划、贪心算法、回溯法三
01背包问题实验报告.doc
01背包问题实验报告 - 算法设计与分析 实验报告书 实验名称: 0/1 背包问题 学 号: 姓 名: 实验时间: 2015 年 6 月 1 日 《算法分析与设计》实...
计算机算法设计与分析实验报告.doc
计算机算法设计与分析实验报告_工学_高等教育_教育...与 0-1 背包问题不同的是,在选择物品 i 装入...文档贡献者 wh200818 贡献于2011-01-31 ...
更多相关标签: