题解 | #0-1背包和完全背包#

【模板】完全背包

http://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc

一、0-1背包

第一类问题：最大价值

确定状态
容量+剩余物品数量
确定选择
针对一个物品放入背包或者不放入背包两种选择
确定dp含义
dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值
确定base case
当物品数量为0或者背包体积为0时，最大价值为0，即dp[0][x]=0,dp[x][0]=0
确定状态转移方程

dp[i][j]=max{dp[i-1][j],w[i]+dp[i-1][j-v[i]]]}

Java实现

public static int max(int n,int V,int[][] vw){
        int[][] dp = new int[n+1][V+1];
        for(int i=0;i<n+1;i++){
            dp[i][0] = 0;
        }
        for(int j=1;j<V+1;j++){
            dp[0][j] = 0;
        }
        for(int i=1;i<n+1;i++){
            for(int j=1;j<V+1;j++){
                if(vw[i-1][0]>j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],vw[i-1][1]+dp[i-1][j-vw[i-1][0]]);
                }
            }
        }
        return dp[n][V];
    }

第二类问题：刚好装满时最大价值

确定状态
容量+剩余物品数量
确定选择
针对一个物品放入背包或者不放入背包两种选择
确定dp含义
dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值
确定base case
当物品数量为0时，若体积大于0，则无法装满，用Integer.MIN_VALUE来表示，当体积为0时，存放最大价值为0，则dp[0][1...x]=Integer.MIN_VALUE,dp[0...x][0]=0
确定状态转移方程

dp[i][j]=max{dp[i-1][j],w[i]+dp[i-1][j-v[i]]]}

Java实现

public static int maxWhenFull(int n,int V,int[][] vw){
      int[][] dp = new int[n+1][V+1];
        for(int i=0;i<n+1;i++){
            dp[i][0] = 0;
        }
        for(int j=1;j<V+1;j++){
            dp[0][j] = Integer.MIN_VALUE;
        }
        for(int i=1;i<n+1;i++){
            for(int j=1;j<V+1;j++){
                if(vw[i-1][0]>j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],vw[i-1][1]+dp[i-1][j-vw[i-1][0]]);
                }
            }
        }
        return dp[n][V]<0?0:dp[n][V];
    }

二、完全背包

第一类问题：最大价值

确定状态
容量+剩余物品数量
确定选择
针对一个物品有k种选择，k=0,1,2....,同时满足k*v[i]<j,就是说k不能无限增大，要考虑背包的容量
确定dp含义
dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值
确定base case
当物品数量为0或者背包体积为0时，最大价值为0，即dp[0][x]=0,dp[x][0]=0
确定状态转移方程

dp[i][j]=max{k*w[i]+dp[i-1][j-k*v[i]]]}

Java实现

    public static int getMax(int n,int V,int[][] vw){
        int[][] dp = new int[n+1][V+1];
        for(int i=0;i<n+1;i++){
            dp[i][0]=0;
        }
        for(int j=0;j<V+1;j++){
            dp[0][j]=0;
        }
        for(int i=1;i<n+1;i++){
            for(int j=1;j<V+1;j++){
                int max = dp[i-1][j];
                for(int k=0;k*vw[i-1][0]<=j;k++){
                    max = Math.max(max,k*vw[i-1][1]+dp[i-1][j-k*vw[i-1][0]]);
                }
                dp[i][j] = max;
            }
        }
        return dp[n][V];
    }

第二类问题：刚好装满时最大价值

确定状态
容量+剩余物品数量
确定选择
针对一个物品有k种选择，k=0,1,2....,同时满足k*v[i]<j,就是说k不能无限增大，要考虑背包的容量
确定dp含义
dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值
确定base case
当物品数量为0时，若体积大于0，则无法装满，用Integer.MIN_VALUE来表示，当体积为0时，存放最大价值为0，则dp[0][1...x]=Integer.MIN_VALUE,dp[0...x][0]=0
确定状态转移方程

dp[i][j]=max{k*w[i]+dp[i-1][j-k*v[i]]]}

Java实现

    public static int getMaxWhenFull(int n,int V,int[][] vw){
        int[][] dp = new int[n+1][V+1];
        for(int i=0;i<n+1;i++){
            dp[i][0]=0;
        }
        for(int j=1;j<V+1;j++){
            dp[0][j]=Integer.MIN_VALUE;
        }
        for(int i=1;i<n+1;i++){
            for(int j=1;j<V+1;j++){
                int max = dp[i-1][j];
                for(int k=0;k*vw[i-1][0]<=j;k++){
                    max = Math.max(max,k*vw[i-1][1]+dp[i-1][j-k*vw[i-1][0]]);
                }
                dp[i][j] = max;
            }
        }
        return dp[n][V]>0?dp[n][V]:0;
    }