AcWing 2. 01背包问题

题目说明

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vi，价值是 wi。

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

输出最大价值。

输入格式

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

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

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例：

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

笔者理解

此题是一道排序算法问题，在AcWing题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题是最经典的背包的问题，也是比较经典的动态规划问题，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.Scanner;
import java.lang.Math;

class Main {
    /*
     * 动态规划
     * 背包问题
     */
    
    // 物品数量和背包容积
    static int N, V;
    
    // 第 i 件物品的体积和价值
    static int[] v, w;


    public static int count() {
        // int[][] dp = new int [N + 1][V + 1];
        
        int[] dp = new int [V + 1];

        // 朴素算法
        // i代表第i件物品
        // j表示当前背包的初始体积
        /*for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                // 不选i - 1件物品
                dp[i][j] = dp[i - 1][j];

                // 如果还能装下第i - 1件物品
                if (j >= v[i - 1]) {
                    // 比较两者的收益，选取收益最大者
                    dp[i][j] = Math.max(dp[i][j], 
                        // i - 1件物品时的最大收益加上第i件物品的价值
                        dp[i - 1][j - v[i - 1]] + w[i - 1]);
                }
            }
        }*/
        
        // 优化算法
        for (int i = 1; i <= N; i++) {
            // 此处简化了空间，使用了滚动数列来实现
            // 因为上述动态规划状态转移时只涉及到i及i - 1层的数据
            // 所以我们尝试将i从循环中剥离
            // 因为i是递增的，而j是递减的
            // 所以上述中的dp[i][j] = dp[i - 1][j]在剥离i是恒成立的
            // 而dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1])在剥离i后变成了
            // dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1])
            // 在运算时，赋值的等式左边是先于右边算出来的，
            // 所以dp[i - 1][j - v[i - 1]] + w[i - 1] 就会被 dp[i][j - v[i - 1]] + w[i - 1]覆盖
            // 所以我们将背包的容量从V开始倒序计算来避免计算时被覆盖
            for (int j = V; j >= 0; j--) {
                if (j >= v[i - 1]) {
                    dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
                }
            }
        }

        // return dp[N][V];
        
        return dp[V];
    }

    public static void main(String[] agrs) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        V = sc.nextInt();

        v = new int[N];
        w = new int[N];

        for (int i = 0; i < N; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        sc.close();

        System.out.println(count());
    }
}

总结

本题是今天的一题，难度是为简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。