一、0-1背包

第一类问题：最大价值

  1. 确定状态
    容量+剩余物品数量
  2. 确定选择
    针对一个物品放入背包或者不放入背包两种选择
  3. 确定dp含义
    dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值
  4. 确定base case
    当物品数量为0或者背包体积为0时，最大价值为0，即dp[0][x]=0,dp[x][0]=0
  5. 确定状态转移方程
dp[i][j]=max{dp[i-1][j],w[i]+dp[i-1][j-v[i]]]}
  1. 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];
    }

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

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

二、完全背包

第一类问题：最大价值

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

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

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

三、总结

0-1背包是完全背包的特殊情况!
刚好装满时最大价值与直接最大价值的区别在于base case初始化的不同！