0-1背包问题（java实现）

给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

public int knapsack(int W,int N,int[] wt,int[] val){
    int[][] dp = new int[N+1][W+1];
    //重量为0时最大价值为0
    for(int i = 0;i <= N;i++){
        dp[i][0] = 0;
    }
    //物品个数为0是最大价值为0
    for(int i = 0;i <= W;i++){
        dp[0][i] = 0;
    }
    for(int i = 1;i <= N;i++){
        for(int w = 1;w <= W;w++){
            if(w - wt[i-1] < 0){
                //装不下第i个物品(第i个物品的wt其下标为i-1)
                dp[i][w] = dp[i-1][w];
            }else {
                //选择装第i个物品或者不装第i个物品
                dp[i][w] = Math.max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1]);
            }
        }
    }
    return dp[N][W];
}

说明：dp[i] [w]表示前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是d[i] [w]