01背包问题

题目

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。

思路

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        final int N = 1024;
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // n个物品
        int m = input.nextInt(); // 包容量为m
        int[][] f = new int[N][N];// 总价值
        int[] w = new int[N];// 单个重量
        int[] v = new int[N];// 单个价值

        for (int i = 1; i <= n; i++) {
            w[i] = input.nextInt();
            v[i] = input.nextInt();

        }
        input.close();
        //规则
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 不取第i件
                f[i][j] = f[i - 1][j];
                //取第i件
                if (j >= w[i]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]);
                }
            }
        }

        int res = 0;
        for (int i = 0; i <= m; i++) {
            res = Math.max(res, f[n][i]);
        }
        System.out.println(res);
    }

}