01背包（动规）

解题思路:

依旧还是按照动规五部曲
1.创建dp数组 ，dp[i][j]：是当背包容量为j时放入的最大价值； i代表的是：第i个物品
2.递推公式：可以分为两种情况：

   2.1当背包容量j小于当前物品i占用的空间，则直接取上有个物品i-1

   2.2当背包容量j大于当前物品i占用的空间，直接放入物品i，放入后看·剩余空间然后从上一次的查找即可

3.初始化dp[i][j] ,初始化第一个物品时的最大价值即可，当j=weight[0]时的情况

4.遍历顺序从左到右，从上到下

5.打印dp数组

注意事项:

初始化时需要特别注意

分清楚初始化和i,j所代表的含义

参考代码:

package com.wyh.Test;

import java.util.Scanner;

public class Knapsack {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       //物品个数
       int n = scanner.nextInt();
       //背包容量
       int w = scanner.nextInt();
       //记录物品的重量
       int[] weight = new int[n];
       //记录物品的价值
       int[] val = new int[n];
       for (int i = 0; i < n; i++) {
           weight[i] = scanner.nextInt();
           val[i] = scanner.nextInt();
       }
       System.out.println(knapsack(weight, val, n, w));
   }

   public static int knapsack(int[] weight, int[] val, int n, int bigSize) {
       //创建dp数组
       int[][] dp = new int[n][bigSize + 1];
       //初始化
       for (int j = weight[0]; j <= bigSize; j++) {
           dp[0][j] = val[0];
       }
       //其他就不需要初始化，本来就是0
       for (int i = 1; i < n; i++) {
           for (int j = 1; j <= bigSize; j++) {
               //当当前物品i容量>背包容量j时
               if (j < weight[i]) {
                   dp[i][j] = dp[i - 1][j];
               } else { //当当前物品i容量小于背包容量j  ，有两种情况：
                   //1.当不放入物品i时的价值
                   //2.当放入当前物品时
                   dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + val[i]);
               }
           }
       }

//分析错误
//        for (int i=0;i<n;i++){
//            for (int j=0;j<=bigSize;j++){
//                System.out.print(dp[i][j]+" ");
//            }
//            System.out.println();
//        }

       return dp[n - 1][bigSize];
   }


}