背包问题

背包问题属于典型的动态规划问题。这里我们将详细介绍0-1背包，完全背包和多重背包问题

一、 0-1背包

有N件物品和一个容量为V的背包。第i件物品的体积是volume[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，我们尝试用动态规划来解决。
我们考虑，当向一个背包中放入物体时，有放和不放两种方法。设maxValue[i][j]表示放入第i个物体，背包体积容量为j时的最大价值，则有

//在背包容量可放入的情况下
maxValue[ i ][ j ] = Math.max(maxValue[ i - 1 ][ j ], maxValue[i - 1][ j - volume[ i ] ] + value[ i ]);
// 若 j< volume[ i ]
maxValue[ i ][ j ] = maxValue[ i - 1 ][ j ]

据此我们可以轻松的写出对应的代码

/**
     * @param v      背包容量
     * @param volume 物品体积
     * @param value  物品价值
     * @return
     */
    public static int[][] getMaxValue(int v, int[] volume, int[] value) {
        int n = volume.length;
        int q = -1;
        /**初始化数组
         *
         */
        int[][] maxValue = new int[n+1][v+1];
        // 当放入一个物品，背包容量为j时的情况
        for (int j = 0; j <= v; j++) {
            for (int i = 0; i < n; i++) {
                q = Math.max(q, maxValue[1][j] = (j >= volume[i]) ? value[i] : 0);
                maxValue[1][j] = q;
            }
        }
        //向背包中放入物品
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= v ; j++) {
                if (j >= volume[i-1]){
                maxValue[i][j] = Math.max(maxValue[i - 1][j], maxValue[i - 1][j - volume[i-1]] + value[i-1]);
                }else {
                    maxValue[i][j] = maxValue[i - 1][j];
                }
            }
        }


        return maxValue;
    }

    public static void main(String[] args) {
        int[] volume = {1,2,2,4,6};
        int[] value = {3,2,5,4,6};
        int[][]  maxValue=getMaxValue(7, volume, value);
        System.out.println(maxValue[5][7]);

    }
输出结果为12

二、完全背包问题

有N种物品和一个容量为V的背包。每种物品都有无限件可用，每种体积是volume[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
01背包在选第i个物品时，容积够用情况下，只有2种状态可选，放还是不放，找出最大价值的选择
完全背包在选第i种物品时，容积够用情况下，可能有2种以上状态可选，放1个，或者2个，3个，或者不放。找出最大价值的选择
这里状态方程转化为

//这里满足n*volume[i]<j
maxValue[i][j] = Math.max(maxValue[i-1][j], maxValue[i-1][j-n*volume[i]]+n*value[i])

代码如下

 /**
     *
     * @param v  背包容量
     * @param volume 第i种物品的体积
     * @param value  第i中物品的价值
     * @return
     */
    public static int[][] getMaxValue(int v, int[] volume, int[] value) {
        int n = volume.length;
        int[][] maxValue = new  int[n+1][v+1];
        // 初始化maxValue 第一种物品 体积为i时的最大价值
        for (int i = 0; i <= v ; i++) {
            int j = i / volume[0];
            maxValue[1][i] = j * value[0];
        }
        //第i种物品体积为j时的价值
        for (int i = 2; i <= n  ; i++) {
            for (int j = 0; j <= v  ; j++) {
                if (j > volume[i-1])
                maxValue[i][j] = Math.max(maxValue[i - 1][j],
                        maxValue[i - 1][j - (j / volume[i - 1])*volume[i-1]] + (j / volume[i - 1]) * value[i - 1]);
                else {
                    maxValue[i][j] = maxValue[i - 1][j];
                }
            }
        }
        return maxValue;

    }

    public static void main(String[] args) {
        int[] volume = {2, 2, 4, 3, 6};
        int[] value = {4, 3, 10, 7, 13};
        int[][] maxValue = getMaxValue(10, volume, value);
        System.out.println(maxValue[5][10]);
    }

三、多重背包问题

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件体积是volume[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
解法1：
我们可将其转化为0-1背包问题
解法2：
状态转移方程

maxValue[i][j] = Math.max(maxValue[i-1][j], maxValue[i-1][j-n*volume[i]]+n*value[i])

在0-1背包的基础上，添加一下内容

int nCount = min(A[i], w / wt[i]);
//第三层循环
for(int k = 0; k <= nCount; k++)
{
    M[i][w] = max(M[i][w], k * value[i] + M[i - 1][w - k * wt[i]]);
}