现在的位置: 首页 > 编程技术 > 算法学习 > 正文

一道关于背包的算法题

2015年11月24日 算法学习 ⁄ 共 1832字 ⁄ 字号 一道关于背包的算法题已关闭评论 ⁄ 阅读 693 次

背包问题,1, 2, 3….i个物品,重量为Wi,价值为Vi 我们将在总重量不超过Y 的前提下,前i 种物品的总价值所能达到的最高值定义为MaxV(i , Y )。

MaxV(i , Y )的递推关系为:

  • MaxV (0, Y ) = 0
  • MaxV (i , 0) = 0
  • 如果Wi > Y , MaxV (i , Y ) = MaxV (i - 1, Y )
  • 如果Wi ≤ Y , MaxV (i , Y ) = max { MaxV (i - 1, Y ), Vi + MaxV (i - 1, Y - Wi ) }

max用以计算最大值,前一个参数是指不放入物品i的总价值,后一个参数表示在可以放入i时
已有的价值加上物品i的价值通过计算MaxV(n , W)即得到最终结果。

 1 public class knapsack {
 2     /* 背包最大负重 */
 3     public static final int MAX_WEIGHT = 5;
 4 
 5     private static class Item {
 6         public int weight;
 7         public int value;
 8 
 9         public Item(int w, int v) {
10             weight = w;
11             value = v;
12         }
13     }
14 
15     public static void main(String[] args) {
16         // 物品清单
17         Item[] items = { new Item(0, 0), new Item(2, 12), new Item(1, 10),
18                 new Item(3, 20), new Item(2, 15) };
19         // 有itemList行,MAX_WEIGHT+1列的二维数组
20         int[][] maxValue = new int[items.length][MAX_WEIGHT + 1];
21 
22         fillMaxValue(items, maxValue);
23         // 此时maxValue也完成赋值
24         // 可以回溯求出最优解
25         weSelect(items, maxValue);
26     }
27 
28     static void weSelect(Item[] items, int[][] maxValue) {
29         int N = items.length;
30         // 背包剩余空间
31         int remainSpace = MAX_WEIGHT;
32         for (int i = N - 1; i > 0; i--) {
33             if (remainSpace >= items[i].weight) { // 剩余空间可以放入当前物品i
34                 // 总价值减去可以放入物品i时的总价值, remainValue为所剩价值
35                 int remainValue = maxValue[i][remainSpace]
36                         - maxValue[i - 1][remainSpace - items[i].weight];
37                 if (remainValue == items[i].value) {
38                     // remainValue与物品i的价值相等,说明是选择的一部分
39                     remainSpace -= items[i].weight;
40                     System.out.println("Item" + i + " is part of selection");
41                 }
42             }
43         }
44     }
45 
46     static void fillMaxValue(Item[] items, int[][] maxValue) {
47         // 没有物品放入,价值为0,即二维数组的第一行全部置0
48         for (int w = 0; w <= MAX_WEIGHT; w++)
49             maxValue[0][w] = 0;
50 
51         for (int i = 1; i < items.length; i++) {
52             maxValue[i][0] = 0; // 背包负重为0,最大价值为0
53             for (int w = 1; w <= MAX_WEIGHT; w++) {
54                 int before = maxValue[i - 1][w]; // 物品没有放入时的总价值
55                 if (items[i].weight <= w) { // 当前物品可以放入背包
56                     int after = items[i].value
57                             + maxValue[i - 1][w - items[i].weight];
58                     maxValue[i][w] = Math.max(before, after);
59                 } else  // 当前物品不能放入背包,总价值保持不变
60                     maxValue[i][w] = before;
61             }
62         }
63         System.out.println("Given a pack can hold " + MAX_WEIGHT + "\n"
64                 + "The max value we can get is: "
65                 + maxValue[items.length - 1][MAX_WEIGHT]);
66     }
67 }

抱歉!评论已关闭.