动态规划

***原文声明：本文是本人根据宫水三叶的博文整理的随笔，关注原文请移步至：宫水三叶

背包问题

**0-1背包问题：**题目描述：有N件物品和一个容量为V的背包。每件物品有且只有1件。第i件物品的体积是v[i],价值是W[i]。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

1、dp[N][C+1]解法：

对于着了问题，如果设计DFS(int []v,int []w,int i,int c);其中v 和w 是不变参数不必关心。i和c分别表示当前枚举到哪件物品和现在剩余的容量。返回值为最大价值。

定义状态：dp[i][c]考虑前i件物品且容量不超过C的最大价值。

不选：其实就是dp[i-1][c]

选择：dp[i-1][c-v[i]]+w[i]前提是当前剩余容量>=物品的体积。

状态转移方程：dp[i][c]=max(dp[i-1][c],dp[i-1][c-v[i]]+w[i])

class Solution{
    public int maxValue(int N,int C,int []v,int []w){
        int [][]dp=new int[N][C+1];
        //第一件
        for(int i=0;i<=C;i++){
            dp[0][i]=i>=v[0]?w[0]:0;
        }
        for(int i=1;i<N;i++){
            for(int j=0;j<C+1;j++){
                //不选该物品
                int n=dp[i-1][j];
                //选择
                int y=j>=v[i]?dp[i-1][j-v[i]]+w[i]:0;
                dp[i][j]=Math.max(n,y);
            }
        }
        return dp[N-1][C];
    }
}

优化1：由于计算第i行格子，只需要第i-1行格子的数据，因此可以使用dp[2][C+1]滚动数组，使用维度的地方进行i&1或者i%2运算即可。

优化2：计算第i行格子时，不仅只依赖于i-1行，而且只依赖于i-1行的第c个格子和c-v[i]个格子。因此我们将求解第i行格子的顺序【从0到c]改为【从c到0】。可以将原来的二维数组压缩到一行。

class Solution{
    public int maxValue(int N,int C,int[]v,int []w){
        int []dp=new int[C+1];
        for(int i=0;i<N;i++){
            for(int j=C;j>=V[i];j--){
                //不选
                int n=dp[j];
                //选择
                int y=dp[j-v[i]]+w[i];
                dp[j]=Math.max(n,y);
            }
        }
        return dp[C];
    }
}

**背包问题：**在0-1背包的基础上，物品的有无限件，可以多次选择。

因此，dp[i][j]表示考虑前i件物品放入容量为j的背包，获得最大的价值。由于物品可以多次选择，因此dp[i][j]就是[0-k]件，dp[i-1][j-k*v[i]]+k*w[i]的最大值。

状态转移方程：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*v[i]]+k*w[i]),0<k*v[i]<=j

class solution{
    public int maxValue(int N,int C,int[]v,int []w){
        int dp[][]=new int[N][C+1];
        for(int j=0;j<=C;j++){
            int maxk=j/v[0];
            dp[0][j]=maxK*w[0];
        }
        for(int i=1;i<N;i++){
            for(int j=0;j<=C;j++){
                int n=dp[i-1][j];
                int y=0;
                for(int k=1;;k++){
                    if(j<v[i]*k)break;
                }
                y=Math.max(y,dp[i-1][j-k*v[i]]+k*w[i]);
            }
            dp[i][j]=Math.max(n,y);
        }
    }
    return dp[N-1][C];
}
//时间复杂度O(N*C*C),空间复杂度O(C*N)

一维空间优化：

dp[i][j]=dp[i-1][j-k*v[i]]+k*w[i],0<k*v[i]<=j

dp[i][j-v[i]]=dp[i-1][j-(k-1)*v[i]]+k*w[i],0<k*v[i]<=j

对应于dp[i][j]和d[i][j-v[i]],两式具有部分等差性，即部分对应总是相差w[i]。

因而dp[i][j]最大值的问题转化为dp[i][j-v[i]]+w[i]的最大值。==>dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])

消除i的维度，dp[j]=max(dp[j],dp[j-v[i]]+w[i])

所以计算dp[j]时需要保证dp[j-v[i]]已经保存好。因此将j的遍历顺序改为从小到大即可。以保证使用dp[j-v[i]]计算dp[j]的时候，dp[j-v[i]]的值不会更新。

class solution{
    public int maxValue(int N,int C,int[]v,int []w){
        int []dp=new int[C+1];
        for(int i=0;i<N;i++){
            for(int j=0;j<=C;j++){
                int n=dp[j];
                int y=j-v[i]>=0?dp[j-v[i]]+w[i]:0;
                dp[i][j]=Math.max(n,y);
            }
        }
        return dp[C];
    }
}
//时间复杂度O(N*C),空间复杂度O(C)