小阅的阅读计划

[题目链接](https://www.nowcoder.com/practice/3fab21c915b74a15a591d6c8ce5735ff)

思路

本题是经典的 0/1 背包问题。有 $n$ 本书，每本书有一个花费 $c$ （所需阅读积分）和价值 $v$ （收益），总共有 $s$ 个阅读积分，每本书最多选一次，求能获得的最大价值。

动态规划

定义 $dp[j]$ 表示恰好使用 $j$ 个阅读积分时能获得的最大价值。初始时 $dp[0] = 0$ ，其余为 $0$ 。

对于每本书 $(c_i, v_i)$ ，从大到小枚举容量 $j$ （从 $s$ 到 $c_i$ ），进行转移：

$ $dp[j] = \max(dp[j],\ dp[j - c_i] + v_i)$ $

为什么要倒序枚举？ 因为是 0/1 背包，每本书只能选一次。如果正序枚举， $dp[j - c_i]$ 可能已经包含了当前这本书的贡献，相当于同一本书被选了多次。倒序枚举保证更新 $dp[j]$ 时， $dp[j - c_i]$ 还是上一轮（不包含当前书）的状态。

最终答案为 $dp[s]$ 。

举例

以样例 2 为例， $s = 10, n = 5$ ，5 本书分别为 $(6,8), (4,10), (2,4), (4,5), (3,5)$ 。

最优方案是选第 2、3、4 本书，花费 $4 + 2 + 4 = 10$ ，价值 $10 + 4 + 5 = 19$ 。

复杂度

时间复杂度： $O(n \times s)$ ，其中 $n \le 500$ ， $s \le 10000$ ，完全可以接受。
空间复杂度： $O(s)$ ，使用一维滚动数组。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int s, n;
    scanf("%d%d", &s, &n);
    vector<int> dp(s + 1, 0);
    for(int i = 0; i < n; i++){
        int c, v;
        scanf("%d%d", &c, &v);
        for(int j = s; j >= c; j--){
            dp[j] = max(dp[j], dp[j - c] + v);
        }
    }
    printf("%d\n", dp[s]);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int n = sc.nextInt();
        int[] dp = new int[s + 1];
        for (int i = 0; i < n; i++) {
            int c = sc.nextInt();
            int v = sc.nextInt();
            for (int j = s; j >= c; j--) {
                dp[j] = Math.max(dp[j], dp[j - c] + v);
            }
        }
        System.out.println(dp[s]);
    }
}

import sys
input = sys.stdin.readline

s, n = map(int, input().split())
dp = [0] * (s + 1)
for _ in range(n):
    c, v = map(int, input().split())
    for j in range(s, c - 1, -1):
        dp[j] = max(dp[j], dp[j - c] + v)
print(dp[s])

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [s, n] = lines[0].split(' ').map(Number);
    const dp = new Array(s + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const [c, v] = lines[i + 1].split(' ').map(Number);
        for (let j = s; j >= c; j--) {
            dp[j] = Math.max(dp[j], dp[j - c] + v);
        }
    }
    console.log(dp[s]);
});