题解

题面分析

在双11大促销中，商城共有 $M$ 种商品，每种商品限购两件，原始价格为 $X$ 元，购买一件的折扣价为 $Y$ 元，购买两件的折扣价为 $Z$ 元，其中满足 $X \geq Y \geq Z$。小明的银行卡余额为 $N$ 元。在不超过 $N$ 元的预算内，如何购买商品才能获得最大的优惠金额？

问题转化

本问题可以转化为 多重背包问题。具体来说：

• 背包容量：小明的银行卡余额 $N$ 元。
• 物品种类：每种商品视为一种物品，每种商品有三种选择（不购买、购买一件、购买两件）。
• 物品属性：
  • 不购买：花费 0 元，优惠 0 元。
  • 购买一件：花费 $Y$ 元，优惠 $X - Y$ 元。
  • 购买两件：花费 $2 \times Z$ 元，优惠 $2 \times X - 2 \times Z$ 元。

目标是选择购买方案，使得在不超过 $N$ 元的预算内，获得的总优惠金额最大化。

详细思路

1. 定义状态

使用一个一维动态规划数组 dp[j]，表示在花费不超过 $j$ 元时，能够获得的最大优惠金额。

• 初始化：dp[0] = 0，表示不花钱时的优惠金额为 0。
• 其他状态：初始时，所有 dp[j]（$1 \leq j \leq N$）都设为 0。

2. 状态转移

对于每种商品，考虑三种购买方式，并更新 dp 数组：

• 不购买：不改变 dp[j] 的值。
• 购买一件：
  • 花费：$Y$ 元。
  • 优惠：$X - Y$ 元。
  • 转移：如果当前预算 $j$ 满足 $j \geq Y$，则

dp[j] = max(dp[j], dp[j - Y] + (X - Y))

• 购买两件：
  • 花费：$2 \times Z$ 元。
  • 优惠：$2 \times X - 2 \times Z$ 元。
  • 转移：如果当前预算 $j$ 满足 $j \geq 2 \times Z$，则

dp[j] = max(dp[j], dp[j - 2 * Z] + (2 * X - 2 * Z))

注意：在进行状态转移时，应从高到低遍历预算金额 $j$，以避免在同一商品的不同购买方式之间产生重复计算。

3. 实现细节

• 遍历顺序：对于每种商品，先考虑购买两件，再考虑购买一件，最后是不购买。这是为了确保在计算时不会遗漏任何可能的购买组合。
• 避免重复计算：通过从高到低遍历预算金额，可以保证每种商品的购买方式在当前商品处理时只被使用一次。
• 优化空间：使用一维数组 dp 即可满足需求，无需使用二维数组。

4. 边界条件与特殊情况

• 最小预算：题目保证 $N$ 至少可以购买一件商品，因此无需处理无法购买任何商品的情况。
• 商品价格：由于 $X \geq Y \geq Z$，购买两件的总花费 $2 \times Z$ 可能小于或等于购买一件的花费 $Y$。需要根据具体情况选择最优的购买方式。
• 商品数量限制：每种商品最多购买两件，因此在购买两件时应确保不超过限购数量。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int M;
    cin >> M;
    vector<int> X(M), Y(M), Z(M);
    for (int i = 0; i < M; ++i) {
        cin >> X[i] >> Y[i] >> Z[i];
    }
    int N;
    cin >> N;
    vector<int> dp(N + 1, 0); // dp[i]表示花费i元能获得的最大优惠金额

    for (int i = 0; i < M; ++i) {
        vector<pair<int, int>> items; // 每种商品的购买方案
        // 不购买
        items.push_back({0, 0});
        // 购买一件
        int cost1 = Y[i];
        int discount1 = X[i] - Y[i];
        if (cost1 <= N) {
            items.push_back({cost1, discount1});
        }
        // 购买两件
        int cost2 = 2 * Z[i]; // 修正：总成本为2 * Z[i]
        int discount2 = 2 * X[i] - 2 * Z[i]; // 修正：总优惠为2 * (X[i] - Z[i])
        if (cost2 <= N) {
            items.push_back({cost2, discount2});
        }
        // 动态规划，倒序遍历
        for (int j = N; j >= 0; --j) {
            for (auto &item : items) {
                int cost = item.first;
                int discount = item.second;
                if (j >= cost) {
                    dp[j] = max(dp[j], dp[j - cost] + discount);
                }
            }
        }
    }
    cout << dp[N] << endl;
    return 0;
}

python

M = int(input())
X, Y, Z = [], [], []
for _ in range(M):
    xi, yi, zi = map(int, input().split())
    X.append(xi)
    Y.append(yi)
    Z.append(zi)
N = int(input())
dp = [0] * (N + 1)  # dp[i]表示花费i元能获得的最大优惠金额

for i in range(M):
    items = []
    # 不购买
    items.append((0, 0))
    # 购买一件
    cost1 = Y[i]
    discount1 = X[i] - Y[i]
    if cost1 <= N:
        items.append((cost1, discount1))
    # 购买两件
    cost2 = 2 * Z[i]  # 修正：总成本为2 * Z[i]
    discount2 = 2 * X[i] - 2 * Z[i]  # 修正：总优惠为2 * (X[i] - Z[i])
    if cost2 <= N:
        items.append((cost2, discount2))
    # 动态规划，倒序遍历
    for j in range(N, -1, -1):
        for cost, discount in items:
            if j >= cost:
                dp[j] = max(dp[j], dp[j - cost] + discount)

print(dp[N])

java

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int[] X = new int[M];
        int[] Y = new int[M];
        int[] Z = new int[M];
        for (int i = 0; i < M; i++) {
            X[i] = sc.nextInt();
            Y[i] = sc.nextInt();
            Z[i] = sc.nextInt();
        }
        int N = sc.nextInt();
        int[] dp = new int[N + 1]; // dp[i]表示花费i元能获得的最大优惠金额

        for (int i = 0; i < M; i++) {
            ArrayList<int[]> items = new ArrayList<>();
            // 不购买
            items.add(new int[]{0, 0});
            // 购买一件
            int cost1 = Y[i];
            int discount1 = X[i] - Y[i];
            if (cost1 <= N) {
                items.add(new int[]{cost1, discount1});
            }
            // 购买两件
            int cost2 = 2 * Z[i]; // 修正：总成本为2 * Z[i]
            int discount2 = 2 * X[i] - 2 * Z[i]; // 修正：总优惠为2 * (X[i] - Z[i])
            if (cost2 <= N) {
                items.add(new int[]{cost2, discount2});
            }
            // 动态规划，倒序遍历
            for (int j = N; j >= 0; j--) {
                for (int[] item : items) {
                    int cost = item[0];
                    int discount = item[1];
                    if (j >= cost) {
                        dp[j] = Math.max(dp[j], dp[j - cost] + discount);
                    }
                }
            }
        }
        System.out.println(dp[N]);
        sc.close();
    }
}

题目内容

商城双$11$大促销，每种商品限购两件。一共有$M$种商品。每种商品的原始价格为$X$元。买一件折扣价是$Y$元，买两件折扣价是$Z$元。其中$X>=Y>=Z$。小明银行卡里有余额$N$元。在$N$元的范围内怎么购买商品，才可以获得最多的优惠金额?

输入描述

第$1$行:商品种类$M$，$M$的范围是$[1,20]$。

第$2$到$M+1$行:每个商品的原始价格$X$元，购买一件的折扣价$Y$元，购买两件的折扣价$Z$元。 X\Y\Z的范围是$[1,1000]$。

第$M+2$行:小明银行卡余额$N$元。N的范围是$[1,20000]$，$N$元至少可以购买一件商品。

输出描述

输出可以获得的最多优惠金额

样例1

输入

2
10 8 6
8 6 6
20

输出

10

说明

第一个商品买$2$件，第二个商品买$1$件。总共花费$2^*6+6=18$元在$20$元范围内。

第一件商品优惠$8$元($2$件)，第二件商品优惠$2$元($1$件)。总共优惠$10$元。

样例2

输入

3
10 8 4
20 17 13
30 20 10
50

输出

55

说明

第一个商品买$2$件，第二个商品买$1$件第三个商品买$2$件。总共花费$2^*4+17+2^*10=41$元在$50$元范围内。

第一件商品优惠$12$元($2$件)，第二件商品优惠$3$元($1$件)，第三件商品优惠$40$元($2$件)，总共优惠$55$元。