本文共 1384 字，大约阅读时间需要 4 分钟。

问题描述：

给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn） 和 一个承受重量为W的背包，每种物体都可以分割。问怎么选取这些物体，放在的背包中（不超过背包的承重），让所取的子集达到最大价值。

贪心策略：

优先选取性价比最高的物体，也就是 vi/wi 最高的第 i 个物体。当然也有其他的策略，比如优先取 vi 最高的物体、优先取 wi 最低的物体从而尽可能存放更多的东西。

步骤设计：

1）对所有物体按照 vi/wi 进行排序，初始化最大价值maxValue = 0

2）如果背包还有容量的话(W > 0)，首选比值较大的物体(vi，wi)。

若背包剩余容量W ≥ 比值最大的物体的总容量wi，则将物体(vi，wi)整个放入背包、W=W-wi、maxValue=maxValue+vi；

若背包剩余容量W ＜ wi，则将剩下的空间都放入物体(vi，wi)的一部分、W=0、maxValue=maxValue+W / wi * vi。

代码实现：

// 贪心策略public class PkgProblemTest {	public static void main(String[] args) {		double[] w = {7, 3, 4, 5};      // 物体的重量		double[] v = {12, 12, 40, 25};  // 物体的价值		int W = 10;   // 背包承重		int n = 4;    // 物体个数				// 排序		for (int j=0; j<3; j++) {			int max = j;			for (int i=j+1; i<4; i++) {				if ( v[i]/w[i] > v[max]/w[max] ) {					max = i;				}			}						if (max != j) {				swap(v, max, j);				swap(w, max, j);			}		}				// 验证排序是否成功		for (int i=0; i<4; i++) {			System.out.print(v[i]/w[i] + "\t");		}		System.out.println();				// 计算最大价值		double maxValue = 0.0;		while (W > 0) {			for (int i=0; i<4; i++) {				if (w[i] > W) {  // 代码出口					maxValue += W/w[i] * v[i];					W = 0;					//break;				} else {					maxValue += v[i];					W -= w[i];				}			}		}				System.out.println("最大价值为：" + maxValue);			}		// 交换数组两个下标对应的值	public static void swap(double[] arr, int i, int j) {		double tmp = arr[i];		arr[i] = arr[j];		arr[j] = tmp;	}}

运行结果如下所示，

转载地址：http://obnii.baihongyu.com/