1 问题描述

给定一个容量为V的背包和N种物品,每种物品有无限个可用,第i件物品的重量是c[i],收益是w[i],
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大

2 贪心策略预处理

首先需要对可以放进背包的物品进行一个预处理.根据贪心策略,对于两件物品i和j,如果c[i]>c[j]且w[i]<w[j],直接把物品i舍去,这样才符合物美价廉的思维.想要达到这样的目的,需要对所有物品进行这样的处理:

1. 安排一个数组,数组的每个下标对应的是对应重量的物品,每遍历到相同重量物品时,与数组中该位置的值进行比较,只选取较大的值,遍历完成后,数组保存的即为每个重量下的最大价值.
2. 处理完相同重量的,接下来处理不相同重量的物品.第一步中已经将每个重量的最大价值记录下来了,那么就按照下标从小到大遍历这些数据,每遍历一个数据,就记录下来.如果遍历到的值小于或等于该记录值,说明该物品用了更大的重量获取了更小或者相当的价值,不予理睬.如果遍历到的数据大于记录的值,说明该物品用更大的重量获得了更大的价值,将其加入到哈希表中,并更新记录的值.

代码

/**
 * 首先需要对可以放进背包的物品进行一个预处理
 * @param c 每件物品的容量
 * @param w 每件物品的价值
 * @param v 背包容量
 * @return 被选中的物品c-w对
 */
public HashMap<Integer, Integer> preProcess(int[] c, int[] w, int v) {

    if (c.length != w.length) {
        return null;
    } else {
        int[] tong = new int[v + 1];
        //第一个循环选出相同容量中价值最大的物品
        for (int i = 0; i < c.length; i++) {
            tong[c[i]] = Math.max(tong[c[i]], w[i]);
        }
        //第二个循环,按照容量大小遍历,舍弃比临时值小的物品
        int temp = 0;
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int j = 1; j < tong.length; j++) {
            if (tong[j] == 0) {
                continue;
            } else if (tong[j] > temp) {
                temp = tong[j];
                hm.put(j, tong[j]);
            }
        }
        Set<Integer> set = hm.keySet();
        for (Integer key : set) {
            System.out.println(key + ": " + hm.get(key));
        }
        return hm;
    }
}

测试数据
|角标|1| 2 |3|4|5|
|——-|——|——–|
|c | 3| 4 |5|3|6|
|w | 4| 5 |6|3|5|

3 方法一:常规思路

从背包问题一的思路延伸过来,问题一中需要考虑的是第i件物品要不要放入背包中,所以需要比较的是放入和不放入两种结果的值.即

max{f[i-1,v],f[i-1,v-c[i]]+w[i]}

设对于第i个物品,放入的次数是k,则上式相当于取k=0和k=1两种情况.那么考虑变量k的话,表达式为

max{f[i-1,v-kc[i]]+kw[i]}

将k的范围考虑进去,即0≤kc[i]≤v有

f[i,v] = max{f[i-1, v-kc[i]]+kw[i]|0≤kc[i]≤v}

代码

/**
 * 常规思路
 *
 * @param c 每件物品的容量
 * @param w 每件物品的价值
 * @param v 背包容量
 * @return
 */
public int[][] methodOne(int[] c, int[] w, int v) {
    //预处理物品序列
    HashMap<Integer, Integer> hm = preProcess(c, w, v);
    Set<Integer> set = hm.keySet();
    int n = set.size();
    int[] c1 = new int[set.size()];
    int[] w1 = new int[set.size()];
    Object[] setArray = set.toArray();
    for (int i = 0; i < setArray.length; i++) {
        c1[i] = (int) setArray[i];
        w1[i] = hm.get(c1[i]);
    }

    //求解所x(f[i - 1][j - k * c1[i - 1]] + k * w1[i - 1], f[i][j]);
            }
        }
    }
    return f;
}

测试数据
|角标|1| 2 |3|4|5|
|——-|——|——–|
|c | 3| 4 |5|3|6|
| w | 4 | 5 | 6 | 3 | 5 |

4 方法二:转换成01背包问题

01背包问题的最基本思路就是对每个物品只进行0或1的考虑,即放或者不放.完全背包问题中每个物品可以放多次,次数上限为v/c[i]件.因此可以将一件物品放k次的过程转换为 k个完全相同的物品放入背包,这样就转换成了01背包问题.所以转换方法就是将一件物品复制成v/c[i]个完全相同的物品,分别对这些物品进行0或1的决策.

/**
 * 转换成01背包问题,将每个物品拆分成多个相同的物品,然后对这些物品的每一个进行01决策
 * @param c 每件物品的容量
 * @param w 每件物品的价值
 * @param v 背包容量
 * @return f[n][v]的值
 */
public int methodTwo(int[] c, int[] w, int v) {
    //预处理物品序列
    HashMap<Integer, Integer> hm = preProcess(c, w, v);
    Set<Integer> set = hm.keySet();
    int n = set.size();
    int[] c1 = new int[set.size()];
    int[] w1 = new int[set.size()];
    Object[] setArray = set.toArray();
    for (int i = 0; i < setArray.length; i++) {
        c1[i] = (int) setArray[i];
        w1[i] = hm.get(c1[i]);
    }

    //生成新的数组,拆分出所有可能的物品
    ArrayList<Integer> arr_1 = new ArrayList<Integer>();
    ArrayList<Integer> arr_2 = new ArrayList<Integer>();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < v / c1[i - 1]; j++) {
            arr_1.add(c1[i - 1]);
            arr_2.add(w1[i - 1]);
        }
    }

    //根据新的数组,利用01背包问题求解
    int[] f = new int[v + 1];
    System.out.println("新的数组长度: " + arr_1.size());
    System.out.println(arr_1);
    System.out.println(arr_2);
    for (int i = 0; i < arr_1.size(); i++) {
        for (int j = v; j >= arr_1.get(i); j--) {
            f[j] = Math.max(f[j], f[j - arr_1.get(i)] + arr_2.get(i));
        }
    }
    return f[v];
}

所得结果与常规方法一样.

5 方法三:进一步优化

在求解01背包问题的一维数组解法时,有注意到,当内循环是正序时就会发生重复添加第i个物品的情况.

/**
 * 01背包问题的一维形式中内循环是逆序,改为正序即为完全背包
 *
 * @param c 每件物品的容量
 * @param w 每件物品的价值
 * @param v 背包容量
 * @return f[n][v]的值
 */
public int methodThree(int[] c, int[] w, int v) {
    //预处理物品序列
    HashMap<Integer, Integer> hm = preProcess(c, w, v);
    Set<Integer> set = hm.keySet();
    int n = set.size();
    int[] c1 = new int[set.size()];
    int[] w1 = new int[set.size()];
    Object[] setArray = set.toArray();
    for (int i = 0; i < setArray.length; i++) {
        c1[i] = (int) setArray[i];
        w1[i] = hm.get(c1[i]);
    }

    //内循环逆序
    int[] f = new int[v + 1];
    for (int i = 0; i < n; i++) {
        for (int j=c1[i];j<=v;j++) {
            f[j] = Math.max(f[j], f[j-c1[i]]+w1[i]);
        }
    }
    return f[v];
}