01背包贪心算法.doc

0—1 背包问题一、实验目的学习掌贪心算法法思想二、实验内容用分支限定法求解 0—1 背包问题，并输出问题的最优解0—1 背包问题描述如下：给定 n 种物品和一背包物品 i 的重量是 Wi，其价值为 Vi，背包的容量是 c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大三、实验条件Jdk1.5 以上四、需求分析对于给定 n 种物品和一背包在容量最大值固定的情况下，要求装入的物品价值最大化五、基本思想：总是对当前的问题作最好的选择，也就是局部寻优最后得到整体最优总是选择单位价值最高的物品六、详细设计package sunfa;/**** @author Administrator*/import java.util.*;public class Greedy_Algorithm {static Element dd[];static int CurrentV ;static int CurrentC;static StringBuffer stb= new StringBuffer();public static int knapasck(int c, int[] w, int[] v, int[] x) {int n = v.length;Element d [] = new Element[n];for(int i = 0 ;ic)break;else{x[i] = d[i].tag; //x【】中存的是原元素的序号MaxV2 = MaxV2+d[i].value;c = c -d[i].ww;CurrentC =c ;stb.append("选择第 " + d[i].tag + "个当前价值:"+MaxV2+ "剩余容量:"+c+"\n");}}return MaxV2;}}class Element implements Comparable{int ww; //物品重量int value; //物品价值double wv;//物品单位重量的价值int tag;//物品的标志 是第一个物品public Element(int w ,int vv ,int tag){this.tag = tag;this.ww = w;this.value = vv;wv = (double)vv/w;}//对象比较的方法public int compareTo(Object x) {Element temp = (Element)x;double rate = (double)ww/value;double temprate = (double)temp.ww/temp.value;if(rate

不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。