背包问题

动态规划学了一段时间了，dp也做了不少了，但是还是有很多题目就是不会做，可能归根原因就是还是没能一步一步把问题搞透搞懂，所以还是得脚踏实地的练习题目并进行思考，并不是为了刷题而刷题，而是为了搞懂去刷题。今天写一下常见的背包问题，希望以后能做到举一反三，慢慢来吧！

01背包

参考：https://blog.csdn.net/qq_37767455/article/details/99086678

就以这题为例。

首先，这题是一道典型的动态规划题目，肯定是用dp数组去解决，我们先不想什么优化空间，就用最基本的dp去做，对应这题，有number和capacity两个制约条件，要的是价值v最大。

所以，有两维，横坐标是i，代表第i个物品，纵坐标是j，代表空间制约为y。dp【i】【j】就表示当前背包容量为j，前i个物品的最佳组合所对应的价值。

base case是什么呢？dp【0】【..】和dp【..】【0】应该为0，不多解释。

还有，主干其实就是两层for循环，各自从1到终点，然后怎么转移呢？

如果当前i对应的体积，即w【i-1】大于j，那么dp【i】【j】只能等于dp【i-1】【j】；如果小于等于，那么dp【i】【j】还能等于dp【i-1】【j-w【i-1】】+v【i-1】，比较两者的最大值就是dp【i】【j】。

OK，下面我们写代码：

public int maxValue(int n,int cap,int[] w,int[] v){
    int[][] dp = new int[n+1][cap+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cap;j++){
            if(w[i-1]>j)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
        }
    }
    return dp[n][cap];
}

下图是我们得到的dp表，我们怎样根据它去得到最优解的情况呢？

首先，看dp【i】【j】是否等于dp【i-1】【j】，如果等于，说明第i个不含有，递归dp【i-1】【j】

如果不等于，看dp【i】【j】是否等于dp【i-1】【j-w【i-1】】+v【i-1】，等于说明装了第i个商品，则递归dp【i-1】【j-w【i-1】】

直到i为0结束。

int[] isHave = new int[4];//统计是否含有
void find(int i,int j){
    if(i==0) return ;
    if(dp[i][j]==dp[i-1][j]){
        find(i-1,j);//第i个不含有
    }else if(j-w[i-1]>=0 && dp[i][j]==dp[i-1][j-w[i-1]]+v[i-1]){
        isHave[i-1] = 1;
        find(i-1,j-w[i-1]);
    }
}

完全背包问题

上面是01背包问题，意思就是我们不能无限使用物品，只能用零次或者一次，还有另外一种背包问题就是完全背包问题，就是物品是无限的。

那么我们思考一下，这种情况下，该这么办？

其实好像差不多，只不过dp【i】【j】的转移方程好像需要换一下了，我们还是先看看上面的：

如果当前i对应的体积，即w【i-1】大于j，那么dp【i】【j】只能等于dp【i-1】【j】；如果小于等于，那么dp【i】【j】还能等于dp【i-1】【j-w【i-1】】+v【i-1】，比较两者的最大值就是dp【i】【j】。

对应完全背包问题，如果w【i-1】大于j，那么dp【i】【j】只能等于dp【i-1】【j】，这个不用变即可；如果小于等于，因为可重复，dp【i】【j】还能等于dp【i】【j-w【i-1】】+v【i-1】，比较两者的最大值就是dp【i】【j】。

public int maxValue(int n,int cap,int[] w,int[] v){
    int[][] dp = new int[n+1][cap+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cap;j++){
            if(w[i-1]>j)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);
        }
    }
    return dp[n][cap];
}

背包问题的优化可以参考博客：https://zhuanlan.zhihu.com/p/93857890?utm_source=wechat_session

二维数组是可以优化成一维数组的，但是对于01背包和完全背包，第二层的for循环不一样，重复使用的比如完全背包，从小到大递增即可，但是对于01背包最多只能使用1次的话来说，它需要从大到小往前遍历，否则会影响之前的结果。

这一点我其实还有点迷！