算法设计与分析.doc

回溯算法一、实验目的与要求1、掌握01背包问题的回溯算法；2、进一步掌握回溯算法；二、实验题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?三、实验步骤import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;public class BTKnapsack double c;/ 背包重量 int n; / 物品总数 double w;/ 物品重量数组 double p;/ 物品价值数组 double cw; / 当前重量 double cp; / 当前价值 double bestp; / 当前最优价值public double knapsack(double pp, double ww, double cc) c = cc;n = pp.length;cw = 0.0;cp = 0.0;bestp = 0.0;Element q = new Elementn;for (int i = 0; i n; i+) qi = new Element(i + 1, ppi / wwi);Arrays.sort(q, new ElemComparator();p = new doublen + 1;w = new doublen + 1;for (int i = 1; i n) / 达到叶节点bestp = cp;return;if (cw + wi bestp) backtrack(1 + i);/ 计算上界值private double bound(int i) double cleft = c - cw;double bound = cp;/ 以物品单位重量价值递减顺序装入物品while (i = n & wi = cleft) cleft -= wi;bound += pi;i+;/ 装满背包if (i = n) bound += pi * cleft / wi;return bound;public class Element int id;/ 编号double d;/ 单位重量价值public Element(int id, double d) this.id = id;this.d = d;public class ElemComparator implements Comparator public int compare(Object object1, Object object2) Element element1 = (Element) object1;Element element2 = (Element) object2;if (element1.d element2.d) return 1; else return 0;public static void main(String args) String input;String flag;double capacity = 0;double pp;double ww;double bestP=0.0;BTKnapsack btKnapsack=new BTKnapsack();BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do try do System.out.println(请选择数字功能键： 1-输入数据，2-退出系统);flag = in.readLine().trim(); while (!(flag.equals(1) | flag.equals(2);if (flag.equals(2) break;do System.out.println(请输入各物品重量，数据之间必须以顿号间隔分开！);input = in.readLine().trim();input = in.readLine().replaceAll( , ); while (input.equals();if(input.equals(2)break;String datas = input.split(、);int n1 = datas.length;pp=new doublen1;ww=new doublen1;for (int i = 0; i n1; i+) wwi= Double.parseDouble(datasi);do System.out.println(请输入各物品价值，数据之间必须以顿号间隔分开！);input = in.readLine().trim();input = in.readLine().replaceAll( , ); while (input.equals();if(input.equals(2)break;datas= input.split(,);int n2 = datas.length;if(n1!=n2)System.out.println(输入数据个数不一致，重新输入);continue;for (int i = 0; i n1; i+) ppi= Double.parseDouble(datasi);do System.out.println(请输入背包的容量：);input = in.readLine().trim();input = in.readLine().replaceAll( , ); while (input.equals();if(input.equals(2)break;capacity=Double.parseDouble(input);bestP=btKnapsack.knapsack(pp, ww, capacity);System.