0-1背包问题

题目描述

给一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性，其中第i个物品的重量wt[i],
价值为val[i],问此背包装物品，能装的最大价值是多少
例：N=3,W=4
wt=[2,1,3]
val=[4,2,3]

算法思想

定义dp数组dp[i][j] ：对于前i个物品，当前背包容量为j,这种情况下背包可以装的最大价值为dp[i][j]

代码实现

public class package01 {


    public static int bag01(int N,int W,int[] wt,int[] val){
        int[][] dp=new int[N+1][W+1];
        for (int p = 0; p <= N ; p++) {   dp[...][0]=0 当背包容量为0时，此时最大价值为0
            dp[p][0]=0;
        }
        for (int k = 0; k <= W ; k++) {   dp[0][...]=0 当物品个数为0时，此时最大价值为0
            dp[0][k]=0;
        }

        for (int i = 1; i <=N ; i++) {
            for (int j = 1; j <= W; j++) {
                if(j < wt[i-1]){  如果当前背包容量小于要放入的物品i的重量(对应wt数组下标为i-1)
                    dp[i][j]=dp[i-1][j]; 不放入，用子状态更新，此时子状态为前i-1个物品，背包容量还为j，因为物品i没放入
                }else{ 					物品i能放下，比较是不放的价值大，还是放下的价值大？
                    dp[i][j]=Math.max(dp[i-1][j],   不放的价值
                                      dp[i-1][j-wt[i-1]]+val[i-1]);  放入i的价值，此时子状态为i-1个物品，背包容量为j-放入的i物品的重量  +物品i的价值
                }
            }
        }

        return dp[N][W];
    }

    public static void main(String[] args) {
        int N=3,W=4;
        int[] wt= new int[]{2,1,3};
        int[] val= new int[]{4,2,3};

        int MaxValue = package01.bag01(N, W, wt, val);
        System.out.println(MaxValue);        ====>6
    }