19681 01背包

19681 01背包

⭐️难度：中等
🌟考点：动态规划、01背包
📖

📚

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int N = 100010;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] v = new int[1002];int[] w = new int[1002];int[] dp = new int[1002];for (int i = 1; i <= n; i++) {v[i] = sc.nextInt();w[i] = sc.nextInt();}// dpfor (int i = 1; i <= n; i++) {for (int j = m; j >= v[i]; j--) {dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);}}System.out.println(dp[m]);}
}

🍎笔记

二维数组做法

一维数组做法