题目链接

书籍价值最大化

题目描述

小阅有 个阅饼和 本书可供兑换。每本书 需要花费 个阅饼，并能带来 的价值。每本书只能兑换一次。请计算在阅饼总数不超过 的前提下，小阅能获得的最大总价值是多少。

解题思路

这是一个典型的0/1 背包问题，是动态规划领域的经典模型。

  • 背包容量：阅饼总数 。
  • 物品： 本书。
  • 物品重量：每本书的成本 。
  • 物品价值：每本书的价值 。
  • 约束：每本书最多选择一次（0/1）。
  • 目标：最大化所选书籍的总价值。

我们可以使用动态规划来解决。这里采用空间优化后的一维 DP 数组。

1. 状态定义

我们定义一个一维数组 ，其中 表示当阅饼预算（背包容量）恰好为 时，能获得的最大书籍总价值。这个数组的大小为 。

2. 初始化

我们将 数组的所有元素初始化为 0。 表示预算为 0 时，无法兑换任何书籍，价值为 0。

3. 状态转移

我们遍历每一本书，并用这本书的信息来更新 数组。对于第 本书（成本为 ，价值为 ），我们需要考虑在不同的预算 下，是否要兑换这本书。

对于预算 ，我们有两种选择：

  • 不兑换第 本书：最大价值保持为 （这是在考虑前 本书时得到的结果）。
  • 兑换第 本书（前提是 ）：最大价值为 加上用剩余预算 所能获得的最大价值，即 。

我们在两者中取较大值，因此状态转移方程为：

4. 遍历顺序

为了保证每本书只被选择一次（0/1 特性），内层循环（遍历预算 ）必须从后往前（从 到 ）进行。这可以确保在计算 时，所依赖的 尚未被当前这本书更新，它仍然是代表考虑前 本书时的状态。

5. 最终结果

遍历完所有 本书后， 就是在总预算为 的情况下的最大价值。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int s, n;
    cin >> s >> n;

    vector<int> costs(n);
    vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        cin >> costs[i] >> values[i];
    }

    vector<int> dp(s + 1, 0);

    for (int i = 0; i < n; ++i) {
        for (int j = s; j >= costs[i]; --j) {
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    cout << dp[s] << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int n = sc.nextInt();

        int[] costs = new int[n];
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            costs[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }

        int[] dp = new int[s + 1];

        for (int i = 0; i < n; i++) {
            for (int j = s; j >= costs[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }

        System.out.println(dp[s]);
    }
}

import sys

def solve():
    s, n = map(int, sys.stdin.readline().split())
    
    books = []
    for _ in range(n):
        books.append(list(map(int, sys.stdin.readline().split())))

    dp = [0] * (s + 1)

    for cost, value in books:
        for j in range(s, cost - 1, -1):
            dp[j] = max(dp[j], dp[j - cost] + value)
            
    print(dp[s])

solve()

算法及复杂度

  • 算法：动态规划 (0/1 背包问题)
  • 时间复杂度：，其中 是书籍的数量， 是阅饼的总数。我们需要两层循环，外层遍历所有书籍，内层遍历所有可能的预算。
  • 空间复杂度：，我们使用了一个一维数组来存储动态规划的状态。