01背包问题

题目：

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000

0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

看会了，就来试一试吧：经典的01背包问题
哈哈哈，祝你的代码状态为：Accepted
要是还不会就看看这几个大佬的视频讲解吧：黑马程序员(多看几遍，多动动手)、代码随想录中的算法公开课。
文字版的讲解：代码随想录
题解：创建了二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，当背包容量为 j 时所能获得的最大价值，通过这样使用二维数组的动态规划方法，全面地考虑了放入和不放入每个物品的各种情况，最终准确地求出满足条件的背包能够装入物品的最大总价值。
代码：

二维数组dp数组

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 读取物品数量N和背包容积V
    int N = scanner.nextInt();
    int V = scanner.nextInt();

    // 分别用于存储物品的体积和价值，数组下标从1开始使用，方便对应物品编号
    int[] v = new int[N + 1];
    int[] w = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        v[i] = scanner.nextInt();
        w[i] = scanner.nextInt();
    }

    // dp[i][j]表示在前i个物品中，背包容量为j时能获得的最大价值
    int[][] dp = new int[N + 1][V + 1];

    // 初始化边界情况，当没有物品可选（i = 0）时，无论背包容量是多少，最大价值都为0
    for (int j = 0; j <= V; j++) {
        dp[0][j] = 0;
    }

    // 动态规划核心逻辑，通过两层循环来填充dp数组
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j >= v[i]) {
                // 如果背包容量j大于等于第i个物品的体积v[i]，可以选择放或不放该物品
                // 取放与不放该物品能得到的最大价值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            } else {
                // 如果背包容量j小于第i个物品的体积v[i]，无法放入该物品，价值与前i - 1个物品时相同
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 输出在前N个物品中，背包容量为V时能获得的最大价值
    System.out.println(dp[N][V]);

}
}

一维数组：

import java.util.Scanner;
public class KnapsackProblemOneDArray {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 读取物品数量N和背包容积V
    int N = scanner.nextInt();
    int V = scanner.nextInt();

    // 分别用于存储物品的体积和价值
    int[] v = new int[N + 1];
    int[] w = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        v[i] = scanner.nextInt();
        w[i] = scanner.nextInt();
    }

    // dp[j]表示背包容量为j时能获得的最大价值（使用一维数组进行优化）
    int[] dp = new int[V + 1];

    // 动态规划核心逻辑，通过两层嵌套循环来填充dp数组
    for (int i = 1; i <= N; i++) {
        // 注意这里要从V开始逆序遍历到v[i]，避免重复使用更新后的数据
        for (int j = V; j >= v[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    // 输出背包容量为V时能获得的最大价值
    System.out.println(dp[V]);
 }
}