蓝桥杯算法提高VIP-01背包

解题思路:

简单的0-1背包问题。

注意事项:
注意第二层循环时，j要从m到weight[i]依次递减下去。不然会出现同一物品被选多次的场景。（该种情况是完全背包的解题方法）

参考代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
   public static void main(String[] args) throws IOException {
      BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
      String[] s = reader.readLine().split(" ");
      int n = Integer.parseInt(s[0]);//物品的个数
      int m = Integer.parseInt(s[1]);//背包的重量
      int[] weight = new int[n + 1];
      int[] value = new int[n + 1];
      for (int i = 1; i <= n; i++) {
         String[] s1 = reader.readLine().split(" ");
         weight[i] = Integer.parseInt(s1[0]);
         value[i] = Integer.parseInt(s1[1]);
      }
      int dp[] = new int[m + 1];
      for (int i = 1; i <= n; i++) {
         for (int j = m; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
         }
      }
      System.out.println(dp[m]);
   }
}