0-1背包问题和部分背包(fractional knapsack)问题分析 - 点缀星辰 - ITeye技术网站

0-1背包问题和部分背包(fractional knapsack)问题分析 - 点缀星辰 - ITeye技术网站

http://www.cnblogs.com/laifeiyao/p/3491119.html

 [问题]给定n种物品和1个背包，背包允许的最大重量为Capacity。物品i的重量为weight[i]，价值为value[i]。与0-1背包问题(每种物品只有装入背包或不装入背包两种选择)不同的是，在选择物品i装入背包时，可以只装入物品i的一部分。 问应当怎样选择物品装入背包，使背包中的物品的总价值最大？

      [解析]该问题可用贪心法解决，所采取的贪心策略如下：

      (1)计算每种物品的单位重量的价值value[i]/weight[i]

      (2)依照贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

      (3)若将这种物品全部装入背包后，背包仍有剩余容量，则选择单位重量价值次高的物品并尽可能多地装入背包。

      (4)依此策略一直进行下去，直到背包装满为止。

      如果将该贪心策略用于求解0-1背包问题，则不能保证得到最优解。因为在0-1背包问题中，该策略无法保证最终能将背包装满，部分闲置的背包容量使每公斤背包容量的价值降低了。

1. public double selectMax() {  
2.         double maxValue = 0.0;  
3.         int sum = 0;  
4.         int i;  // suppose v is already sorted by v[i]/w[i] 
5.         for(i = 0; i < v.length; i++) {  
6.             if(sum + w[i] < weight) {  
7.                 sum += w[i];  
8.                 maxValue += v[i];  
9.             } else  
10.                 break;  
11.         }  
12.         if(i < v.length && sum < weight) {  
13.            maxValue += (double)(weight - sum) / w[i] * v[i];  
14.         }  
15.   
16.         return maxValue;  
17.     } 

Read full article from 0-1背包问题和部分背包(fractional knapsack)问题分析 - 点缀星辰 - ITeye技术网站