【贪心策略】背包问题

た入场券 2022-04-10 03:49 186阅读 0赞

**问题描述：**

给定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;
    	}
    }

运行结果如下所示，

![20181224175622667.png][]

[20181224175622667.png]: /images/20220403/992068ea7dec4b69a890df66d2c1e2c1.png