0 1背包问题

1. 问题描述

   给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为c。问：应该如何选择装入背包的物品，使得装入
背包中物品的总价值最大？

2. 问题分析

   在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。该问题是子集选取问题。因此解空间可用子集书
来表示。

   在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。
否则将右子树剪去。

   设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r <= bestp时，可剪去右子树。

   计算右子树中解的上界的更好的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分
而装满背包。由此得到的价值是右子树中解的上界。

3. 举例子说明：

  n = 4;
  c = 7;
  pi = [9, 10, 7, 4];
  wi = [3, 5, 2 ,1];
  单位重量价值分别为[3, 2, 3.5, 4];

  则以物品单位重量价值的递减顺序装入物品。先装入物品4， 然后装入物品3， 再装入物品1， 则背包容量剩余为:7-(1+2+3)=1.
最后只能只能装入1/5 = 0.2的物品2。由此得到一个解为x=[1,0.2,1,1]，其相应的价值为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[n];
		Element[] qq = new Element[n];

		// 初始化q[0, n-1]
		for (int i = 1; i <= n; i++) {
			q[i - 1] = new Element(i, pp[i] / ww[i]);
		}

		// 将各物品依单位重量价值从大到小排序
		Arrays.sort(q);
		for (int i = 0; i < n; i++) {
			qq[i] = q[n - i - 1];
		}

		for (int i = 0; i < n; i++) {
			System.out.println(qq[i]);
		}
		System.out.println();
		System.out.println("################################");

		p = new double[n + 1];
		w = new double[n + 1];
		for (int i = 1; i <= n; i++) {
			p[i] = pp[qq[i-1].id];
			w[i] = ww[qq[i-1].id];
		}

		for (int i = 1; i <= n; i++) {
			System.out.print(p[i] + " ");
		}
		System.out.println();
		for (int i = 1; i <= n; i++) {
			System.out.print(w[i] + " ");
		}
		System.out.println();

		// 回溯搜索
		backtrack(1);

		return bestp;
	}

	private static void 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);
		}
	}

	/**
	 * 计算上界
	 * 
	 * @param i
	 * @return
	 */
	private static double bound(int i) {
		double cleft = c - cw; // 剩余容量
		double bound = cp;

		// 以物品单位重量价值递减顺序装入物品
		while ((i <= n) && (w[i] <= cleft)) {
			cleft -= w[i];
			bound += p[i];
			i++;
		}

		// 装满背包
		if (i <= n) {
			bound += p[i] / w[i] * cleft;
		}
		return bound;
	}
}