0-1背包问题

0-1背包问题：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的总容量为c。

问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，因此该问题称为0-1背包问题。

 

该问题的形式化描述是：

 0-1背包问题具有最优子结构性质，可用动态规划法解决。

解法一：

动态规划

算法分析：
 1）设m(i, j)是背包容量为j,可选物品为0,1,...,i时0-1背包问题的最优值。
 2）递归式
 m(i, j) = 0                                               j=0
 m(i, j) = 0                                               i=0 && j < wi
 m(i, j) = vi                                               i=0 && j >= wi
 m(i, j) = m(i-1, j)                                       j < wi
 m(i, j) = max{m(i-1, j), m(i-1, j-wi) + vi}        j >= wi

实现：

/* description:
 * 0-1背包问题  动态规划求解
 * 算法分析：
 * 1）设m(i, j)是背包容量为j,可选物品为0,1,...,i时0-1背包问题的最优值。
 * 2）递归式
 *  m(i, j) = 0										j=0
 *  m(i, j) = 0										i=0 && j < wi
 *  m(i, j) = vi									i=0 && j >= wi
 *  m(i, j) = m(i-1, j)								j < wi
 *  m(i, j) = max{m(i-1, j), m(i-1, j-wi) + vi}		j >= wi
 *
 * auther:cm
 * date:2010/12/1
 */
public class DynamicKnapsack 
{
	//背包容量
	private int c;
	//物品重量数组
	private int[] w;
	//物品价值数组
	private int[] v;
	private int[][] m;
	//记录结果
	private int[] x;
	//最大价值
	private int maxV;

	public DynamicKnapsack(int[] w, int[] v, int c)
	{
		this.w = w;
		this.v = v;
		this.c = c;
		m = new int[w.length][c+1];
		x = new int[w.length];
	}

	
	public void knapsack()
	{
		init();
		for (int i = 1; i < m.length; i++)
		{
			for (int j = 1; j < m[i].length; j++)
			{
				if (j < w[i])
				{
					m[i][j] = m[i-1][j];
				}
				else
				{
					m[i][j] = Math.max(m[i-1][j], m[i-1][j-w[i]] + v[i]);
				}
			}
		}
		maxV = m[m.length - 1][c];
		//System.out.println(maxV + " ");
	}

	//初始化
	private void init()
	{
		for (int i = 0; i < m.length; i++)
		{
			m[i][0] = 0;
		}
		for (int j = 0; j < m[0].length; j++)
		{
			if (w[0] <= j)
			{
				m[0][j] = v[0];
			}
			else
			{
				m[0][j] = 0;
			}
		}
	}

	//得到最优解
	public int[] getResult()
	{
		int tmp = c;
		int i;
		for (i = m.length - 1; i > 0; i--)
		{
			if (m[i][tmp] == m[i-1][tmp])
			{
				x[i] = 0;
			}
			else
			{
				x[i] = 1;
				tmp = tmp - w[i];
			}
		}
		x[i] = (m[0][c] != 0) ? 1 : 0; 
		return x;
	}

	//打印数组m
	public void printM()
	{
		for (int i = 0; i < m.length; i++)
		{
			System.out.println();
			for (int j = 0; j < m[i].length; j++)
			{
				System.out.print(m[i][j] + " ");
			}

		}
	}

	public static void main(String[] args) 
	{
		int[] w = {3, 2, 5, 4, 1};
		int[] v = {6, 5, 7, 3, 5};
		//int[] w = {2, 2, 6, 5, 4};
		//int[] v = {6, 3, 5, 4, 6};
		int c = 10;
		DynamicKnapsack k = new DynamicKnapsack(w, v, c);
		k.knapsack();
		int[] x = k.getResult();
		for (int i = 0; i < x.length; i++)
		{
			System.out.print(x[i] + " ");
		}
		System.out.println();
		k.printM();
	}
}

 测试数据：

c = 10

w:3 2 5 4 1

v: 6 5 7 3 5

运行结果：

1 1 0 1 1

0 0 0 6 6 6 6 6 6 6 6
0 0 5 6 6 11 11 11 11 11 11
0 0 5 6 6 11 11 12 13 13 18
0 0 5 6 6 11 11 12 13 14 18
0 5 5 10 11 11 16 16 17 18 19

 

该算法缺点：

1）要求所给物品的重量是整数

2）当背包容量c很大时，算法时间复杂度很大

 

解法二：

回溯法

算法分析：

0-1背包问题是子集选取问题。一般情况下，0-1背包问题是NP难的。0-1背包问题的解空间可用子集树表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树，当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。

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

 

计算右子树中解的上界的更好方法是将剩余物品以其单位重量价值排序，然后依次装入物品，直至装不下时，在装入物品的一部分而装满背包。由此得到的价值是右子树中解的上界。为了便于计算上界，可先将物品以其单位重量价值由大到小排序，此后只要顺序的考察各物品即可。

 

算法实现如下：

BacktrackKnapsack.java

/*
 * 0-1背包问题
 * 回溯法
 * 0-1背包问题的解空间可用子集树表示。
 * date: 2010/12/13
 * auther:cm
 */
import java.util.Arrays;
import java.util.Collections;
public class BacktrackKnapsack 
{
	//背包容量
	private double c;
	//物品数
	private int count;
	//物品数组
	private Goods[] goods;
	//当前重量
	private double cw;
	//当前价值
	private double cv;
	//当前最优价值
	private double bestv;

	//用于构造最有解
	private int[] x;		//当前解
	private int[] bestx;	//当前最优解

	public BacktrackKnapsack(double c, double[] w, double[] v)
	{
		this.c = c;
		this.count = w.length;
		x = new int[count];
		bestx = new int[count];
		goods = new Goods[count];

		for (int i = 0; i < goods.length; i++)
		{
			goods[i] = new Goods(i, w[i], v[i]);
		}
	}

	//计算最优值
	public double knapsack()
	{
		//按单位重量价值由大到小排序
		Arrays.sort(goods, Collections.reverseOrder());
		backtrack(0);
		return bestv;
	}

	//回溯算法
	private void backtrack(int i)
	{
		//到达叶节点
		if (i >= count)
		{
			System.out.println("到达叶节点..............");
			if (cv > bestv)
			{
				System.out.println("更新数据..............");
				bestv = cv;
				for (int j = 0; j < bestx.length; j++)
				{
					bestx[j] = x[j];
				}
			}
			return;
		}

		//搜索子树
		if ((cw + goods[i].getW()) <= c)
		{
			//进入左子树
			x[goods[i].getId()] = 1;

			cw += goods[i].getW();
			cv += goods[i].getV();
			backtrack(i+1);
			cw -= goods[i].getW();
			cv -= goods[i].getV();
		}

		//搜索右子树,计算上界 裁剪不含最优解的子树
		if (bound(i+1) > bestv)
		{
			backtrack(i+1);
		}
	}

	//计算上界，裁剪不含最优解的子树
	private double bound(int i)
	{
		double cleft = c - cw;
		double bound = cv;

		//以单位重量价值递减顺序装入物品
		while (i < count && goods[i].getW() <= cleft)
		{
			bound += goods[i].getV();
			cleft -= goods[i].getW();
			i++;
		}
		//装满背包
		if (i < count)
		{
			bound += cleft * goods[i].getAverage();
		}
		return bound;

	}

	//返回最优解
	public int[] getResult()
	{
		return bestx;
	}

	//返回最优值
	public double getBestv()
	{
		return bestv;
	}

	//测试
	public static void main(String[] args) 
	{
		double c = 10;
		//double[] w = {2,2,6,5,4};
		//double[] v = {6,3,5,4,6};
		double[] w = {2, 5, 3, 4, 1};
		double[] v = {5, 7, 6, 3, 5};
		BacktrackKnapsack k = new BacktrackKnapsack(c, w, v);
		double best = k.knapsack();
		System.out.println(best);
		int[] result = k.getResult();
		for (int i = 0; i < result.length; i++)
		{
			System.out.print(result[i] + " ");
		}
	}
}

 

物品类

Goods.java

//物品类
public class Goods implements Comparable
{
	//编号
	private int id;
	//重量
	private double w;
	//价值
	private double v;
	//单位重量价值
	private double average;
	
	public Goods(int id, double w, double v)
	{
		this.id = id;
		this.w = w;
		this.v = v;
		average = v / w;
	}
	public int compareTo(Object obj)
	{
		double aver = ((Goods)obj).getAverage();
		if (average > aver)
		{
			return 1;
		}
		else if (average < aver)
		{
			return -1;
		}
		else
		{
			return 0;
		}
	}
	public void setId(int id)
	{
		this.id = id;
	}
	public int getId()
	{
		return id;
	}
	public void setW(double w)
	{
		this.w = w;
	}
	public double getW()
	{
		return w;
	}
	public void setV(double v)
	{
		this.v = v;
	}
	public double getV()
	{
		return v;
	}
	public double getAverage()
	{
		return average;
	}
}

 

测试数据：

c = 10

double[] w = {2, 5, 3, 4, 1};
double[] v = {5, 7, 6, 3, 5};

 

运行结果：

到达叶节点..............
更新数据..............
19.0
1 0 1 1 1