0 1背包问题
1. 问题描述给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为c。问：应该如何选择装入背包的物品，使得装入
背包中物品的总价值最大？
2. 问题分析
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。该问题是子集选取问题。因此解空间可用子集书
来表示。
在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。
否则将右子树剪去。
设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r <= bestp时，可剪去右子树。
计算右子树中解的上界的更好的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分
而装满背包。由此得到的价值是右子树中解的上界。
3. 举例子说明：
n = 4;
c = 7;
pi = ;
wi = ;
单位重量价值分别为;
则以物品单位重量价值的递减顺序装入物品。先装入物品4， 然后装入物品3， 再装入物品1， 则背包容量剩余为:7-(1+2+3)=1.
最后只能只能装入1/5 = 0.2的物品2。由此得到一个解为x=，其相应的价值为22.因此，对于这个实例，最优值不超过22.
4. Java实现
package com.maozj.suanfa;import java.util.Arrays;/** * 0 1背包问题回溯算法 ** @since jdk1.5以上 * @author 毛正吉 * @version 1.0 * @date 2010.05.22 */public class ZeroOneQuestion {/** * @param args */public static void main(String[] args) {double[] pp = { 0, 9, 10, 7, 4 };double[] ww = { 0, 3, 5, 2, 1 };double cc = 7.0;double result = zeroOneQuestion(pp, ww, cc);System.out.println("result=" + result);}private static class Element implements Comparable {int id; // 物品编号double dv; // 单位重量价值private Element(int _id, double _dv) {id = _id;dv = _dv;}public int compareTo(Object o) {int res = 0;double d = ((Element) o).dv;if (dv < d) {res = -1;} else if (dv == d) {res = 0;} else {res = 1;}return res;}public boolean equals(Object o) {return (dv == ((Element) o).dv);}public String toString() {return "id=" + id + ", dv=" + dv;}}static double c; // 背包容量static int n; // 物品数static double[] w; // 物品重量数组static double[] p; // 物品价值数组static double cw; // 当前重量static double cp; // 当前价值static double bestp;// 当前最优价值public static double zeroOneQuestion(double[] pp, double[] ww, double cc) {c = cc;n = pp.length - 1;cw = 0.0;cp = 0.0;bestp = 0.0;// q为单位重量价值数组Element[] q = new Element;Element[] qq = new Element;// 初始化qfor (int i = 1; i <= n; i++) {q = new Element(i, pp / ww);}// 将各物品依单位重量价值从大到小排序Arrays.sort(q);for (int i = 0; i < n; i++) {qq = q;}for (int i = 0; i < n; i++) {System.out.println(qq);}System.out.println();System.out.println("################################");p = new double;w = new double;for (int i = 1; i <= n; i++) {p = pp.id];w = ww.id];}for (int i = 1; i <= n; i++) {System.out.print(p + " ");}System.out.println();for (int i = 1; i <= n; i++) {System.out.print(w + " ");}System.out.println();// 回溯搜索backtrack(1);return bestp;}private static void backtrack(int i) {if (i > n) {bestp = cp;return;}// 搜索子树if (cw + w <= c) {// 进入左子树cw += w;cp += p;backtrack(i + 1);cw -= w;cp -= p;}if (bound(i + 1) > bestp) {// 进入右子树backtrack(i + 1);}}/** * 计算上界 ** @param i * @return */private static double bound(int i) {double cleft = c - cw; // 剩余容量double bound = cp;// 以物品单位重量价值递减顺序装入物品while ((i <= n) && (w <= cleft)) {cleft -= w;bound += p;i++;}// 装满背包if (i <= n) {bound += p / w * cleft;}return bound;}}
页:
[1]