背包问题

总结了五道题

可以背的最大重量

确定状态:
对于任意一个重量m,分为下面的两种情况:
前n-1个物品就可以组成这个重量了,那么加上最后一个物品,也可以组成这个重量m
前n-1个物品可以组成m-A[i]这样的重量,那么加上最后一个物品就正好可以组成这个重量m
子问题:
所以现在就是从问题n个物品可不可以组成重量m,就变成了n-1个物品可不可以组成重量m
状态方程**:
f[i][j]表示i个物品可以不可以拼成重量j
这个方程是十分重要的,不可以写成f[i]用来表示前i个物品可以拼出的最大的重量,而是要把所有的重量情况都列举出来,f[i][0],f[i][1],…f[i][j]才行.
反例如下:
[3,2,4,5] m=10
如果f[3]=7的话,f[4]也就只能等于7,
但是其实最优解是3+2+5,所以上面的求最大可以装的数量其实不是最优解
初始化:

        //初始化
        f[0][0]=true;
        for(int i=1;i<=m;i++){
            f[0][m]=false;//前0本书组成m个
        }

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] a) {
        if(a==null||a.length==0)
            return 0;
        int n=a.length;
        boolean[][] f=new boolean[n+1][m+1];
        //初始化
        f[0][0]=true;
        for(int i=1;i<=m;i++){
            f[0][m]=false;//前0本书组成m个
        }
        int j=0;
        for(int i=1;i<=n;i++){
            for(j=0;j<=m;j++){
                f[i][j]=f[i-1][j];
                //边界情况
                if(j>=a[i-1])
                    f[i][j]=f[i][j]||f[i-1][j-a[i-1]];
            }
        }
        for(int i=m;i>=0;i--){
            if(f[n][i])
                return i;
        }
        return -1;
    }
}

达到重量的组合数

这个和上面的题查不多,只是将状态方程的Boolean换成了int,
以前是看能不能拼成那个重量,下面这个是对于指定重量的拼成的组合数.
和上面的状态转移方程基本是一样的
f[i][j]+=f[i-1][j-a[i-1]]

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int m) {
        if(nums==null||nums.length==0)
            return 0;
        int n=nums.length;
        int[][] f=new int[n+1][m+1];
        f[0][0]=1;
        for(int i=1;i<=m;i++)
            f[0][i]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                f[i][j]=f[i-1][j];
                if(j>=nums[i-1])
                    f[i][j]+=f[i-1][j-nums[i-1]];
            }
        }
        return f[n][m];
    }
}

下面我们来看一下空间优化:
二维数组版本:

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int m) {
        if(nums==null||nums.length==0)
            return 0;
        int n=nums.length;
        int[][] f=new int[2][m+1];
        f[0][0]=1;
        for(int i=1;i<=m;i++)
            f[0][i]=0;
        int old=0,new1=0;
        for(int i=1;i<=n;i++){
            old=new1;
            new1=1-old;
            for(int j=0;j<=m;j++){
                f[new1][j]=f[old][j];
                if(j>=nums[i-1])
                    f[new1][j]+=f[old][j-nums[i-1]];
            }
        }
        return f[new1][m];
    }
}

下面还有一种更加神奇的算法,就是一维数组版本.
那上面的是只用到的上一层的两个数字,一个是上一层的j下标的,一个是上一层的j-a[i]下标的,
我们可以看到因为f[i-1][j]只是使用1次,所以可以从上面一层的最右边的下标开始计算.
在上面的一层上面:f[j]=f[j]+f[j-a[i-1]]
所以,这样就更加简化到了一维数组

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int m) {
        if(nums==null||nums.length==0)
            return 0;
        int n=nums.length;
        int[] f=new int[m+1];
        f[0]=1;
        for(int i=1;i<=m;i++)
            f[i]=0;
        //i还是进行每一行的运算,只是每一次循环这个数组都是变化着的
        for(int i=1;i<=n;i++){
            //注意这里要逆着算
            for(int j=m;j>=0;j--){
                if(j>=nums[i-1])
                    f[j]+=f[j-nums[i-1]];
            }
        }
        return f[m];
    }
}

组合总和(可重复)

求有多少种可能的组合可以拼出target,看似是和上面的那道题是一样的,但是这个题是可以无限的使用物品.
看上去这个题是难了,但是其实是简单了
确定状态:
要求怎么拼出target,target肯定可以由a[0]…a[n]组成的,所以最后一个物品就是a[0]…a[n],
所以问题就变成怎么拼出target-a[0],…target-a[n]
状态方程:
f[i]=f[i-a[0]]+f[i-a[1]]+…+f[i-a[n]]
f[i]代表可以拼出重量i的数量
初始化
f[0]=1

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public int backPackVI(int[] nums, int m) {
        if(nums==null||nums.length==0)
            return 0;
        int n=nums.length;
        int[] f=new int[m+1];
        f[0]=1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<n;j++){
                if(i>=nums[j])
                    f[i]+=f[i-nums[j]];
            }
        }
        return f[m];
    }
}

带价值的背包

这个只是加上一下价值而已.
还是和背包的第一题和第二题一样,状态转移方程都是一样的,
都是f[i][w]表示前i个物品拼出重量是0~w这样的最大价值是什么
如果是-1表示拼不出来,如果不是-1就和原来的值进行比较,选出最大的一个.
我是感觉和之间的题是没有什么区别的
下面还是使用一个一维数组的空间:

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] a, int[] v) {
        if(a.length==0)
            return 0;
        int n=a.length;
        int[] f=new int[m+1];
        //初始化
        f[0]=0;
        for(int i=1;i<=m;i++){
            f[i]=-1;
        }
        for(int i=1;i<=n;i++){
            //这里很重要是倒着来进行的
            for(int w=m;w>=0;w--){
                //要保证重量和时候可以拼出来
                if(w>=a[i-1]&&f[w-a[i-1]]!=-1){
                    //等号左边的都是第i行的，等号右边的都是第i-1行的
                    f[w]=Math.max(f[w],f[w-a[i-1]]+v[i-1]);
                }
            }
        }
        int res=0;
        for(int i=0;i<=m;i++){
            if(f[i]!=-1)
                res=Math.max(res,f[i]);
        }
        return res;
    }
}

最后是找到前N个物品可以拼出的最大的价值

带价值的背包(可重复)

这道题和上面的一样还是求价值,只是变成了物品可以重复而已

状态方程

这种背包类型的动态规划都是相同的,最后一步都是看最后一个物品是不是进入背包.
最后一个物品不进入,f[i][w]=f[i-1][w]
最后一个物品进入,进入一个:f[i][w]=f[i-1][w-a[i-1]]+v[i-1]
,进入两个:f[i][w]=f[i-1][w-2a[i-1]]+2v[i-1]
,进入三个:f[i][w]=f[i-1][w-3a[i-1]]+3v[i-1]
所以最后就是求这些情况的最大值:
Math.max{ f[i-1][w-ka[i-1]]+kv[i-1]}0<=k<=w/a[i-1]

优化时间复杂度

但是上面的时间复杂度就是太大了,可以达到O(MMN)
所以,我们最好想到一些方法来进行优化一下:

所以,f[i][w]=Math.max(f[i-1][w],f[i][w-a[i-1]]+v[i-1])

优化空间复杂度

从上面的优化过的时间复杂度我们可以看出,这个新的值只和它的上面的一行和左边的一行有关.

所以我们就可以优化成一维数组,

//左边的f[w]是等待着要赋予新值的,右边的f[w]是老值.
//f[w-a[i-1]]是新值,f[w]前面的都是新值
f[w]=Math.max(f[w],f[w-a[i-1]]+v[i-1]);

代码

我们看到这个代码是和上面的一题完全一样的,只是上面的for循环是从右向左,这个是从左向右

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackIII(int[] a, int[] v,int m) {
        if(a.length==0)
            return 0;
        int n=a.length;
        int[] f=new int[m+1];
        //初始化
        f[0]=0;
        for(int i=1;i<=m;i++){
            f[i]=-1;
        }
        for(int i=1;i<=n;i++){
            //这里很重要是正着来进行的,因为我们要用到新的值而不是老值
            for(int w=0;w<=m;w++){
                //要保证重量和时候可以拼出来
                if(w>=a[i-1]&&f[w-a[i-1]]!=-1){
                    //左边的f[w]是等待着要赋予新值的,右边的f[w]是老值.
                    //f[w-a[i-1]]是新值,f[w]前面的都是新值
                    f[w]=Math.max(f[w],f[w-a[i-1]]+v[i-1]);
                }
            }
        }
        int res=0;
        for(int i=0;i<=m;i++){
            if(f[i]!=-1)
                res=Math.max(res,f[i]);
        }
        return res;
    }
}