Book Shop 题解

题目描述

https://cses.fi/problemset/task/1158

给定 n 本书，每本书有价格 $h_i$ 和页数 $s_i$，总预算为 x，求在预算范围内能获得的最大页数。每本书只能购买一次。

限制： - 1 ≤ n ≤ 1000 - 1 ≤ x ≤ $10^5$ - 1 ≤ h_i, s_i ≤ 1000

示例： - 输入：4 10, h = [4, 8, 5, 3], s = [5, 12, 8, 1] - 输出：13（购买第 1 和第 3 本书，价格 4+5=9，页数 5+8=13）

---

解法

问题类型：0-1 背包（每本书只能选一次）

定义：dp[j] 为花费不超过 j 时能获得的最大页数

初始条件：dp[j] = 0（不选任何书时页数为 0）

状态转移： $$dp[j] = \max(dp[j], dp[j - h_i] + s_i)$$

解释：对于每本书，尝试将其加入背包。倒序遍历 j 确保每本书只被使用一次。

代码

n, x = map(int, input().split())
cost = [int(x) for x in input().split()]
pages = [int(x) for x in input().split()]

dp = [0] * (x + 1)

for i in range(n):
    for j in range(x, cost[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - cost[i]] + pages[i])

print(dp[x])

时间复杂度：O(n × x) 空间复杂度：O(x)

注意：0-1 背包需要倒序遍历，确保每本书只选一次；完全背包则正序遍历。