题解 | #购物单#

购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

解题思路

数据结构设计
- 使用二维数组dp[i][j]表示前i个物品在预算为j时的最大满意度
- 每个物品有三种状态：
  - 不买
  - 只买主件
  - 买主件和附件
物品分类
- 主件：可以单独购买
- 附件：必须和其主件一起购买
状态转移
- 如果当前物品是主件：
  - 不买：dp[i][j] = dp[i-1][j]
  - 买：dp[i][j] = max(dp[i][j], dp[i-1][j-v] + v*w)
- 如果当前物品是附件：
  - 需要考虑与主件一起购买的情况
实现步骤
- 初始化dp[0][...]为0
- 遍历每个物品，根据其是主件还是附件更新dp数组
- 最终dp[m][N]即为最大满意度

代码

c++
java
python

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    n /= 10;
    vector p(61, vector<int>(3, 0));  // 价格
    vector level(61, vector<int>(3)); // 重要程度
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a /= 10;
        b *= a;
        if (c == 0) {
            p[i][0] = a;
            level[i][0] = b;
        } else {
            if (p[c][1] == 0) {
                p[c][1] = a;
                level[c][1] = b;
            } else {
                p[c][2] = a;
                level[c][2] = b;
            }
        }
    }
    // 使用分组背包
    vector dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int a = p[i][0], b = level[i][0];
            int c = p[i][1], d = level[i][1];
            int e = p[i][2], f = level[i][2];
            dp[i][j] = j >= a ? max(dp[i - 1][j - a] + b, dp[i - 1][j]) : dp[i - 1][j];
            dp[i][j] = j >= (a + c) ? max(dp[i - 1][j - a - c] + b + d, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a + e) ? max(dp[i - 1][j - a - e] + b + f, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a + c + e) ? max(dp[i - 1][j - a - c - e] + b + d + f, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a + c + e) ? max(dp[i - 1][j - a - c - e] + b + d + f, dp[i][j]) : dp[i][j];
        }
    }
    cout << dp[m][n] * 10 << endl;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        n /= 10;
        
        int[][] p = new int[61][3];  // 价格
        int[][] level = new int[61][3]; // 重要程度
        
        for (int i = 1; i <= m; ++i) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            a /= 10;
            b *= a;
            if (c == 0) {
                p[i][0] = a;
                level[i][0] = b;
            } else {
                if (p[c][1] == 0) {
                    p[c][1] = a;
                    level[c][1] = b;
                } else {
                    p[c][2] = a;
                    level[c][2] = b;
                }
            }
        }
        
        // 使用分组背包
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int a = p[i][0], b = level[i][0];
                int c = p[i][1], d = level[i][1];
                int e = p[i][2], f = level[i][2];
                dp[i][j] = j >= a ? Math.max(dp[i - 1][j - a] + b, dp[i - 1][j]) : dp[i - 1][j];
                dp[i][j] = j >= (a + c) ? Math.max(dp[i - 1][j - a - c] + b + d, dp[i][j]) : dp[i][j];
                dp[i][j] = j >= (a + e) ? Math.max(dp[i - 1][j - a - e] + b + f, dp[i][j]) : dp[i][j];
                dp[i][j] = j >= (a + c + e) ? Math.max(dp[i - 1][j - a - c - e] + b + d + f, dp[i][j]) : dp[i][j];
            }
        }
        
        System.out.println(dp[m][n] * 10);
    }
}

n, m = map(int, input().split())
n //= 10

p = [[0] * 3 for _ in range(61)]  # 价格
level = [[0] * 3 for _ in range(61)]  # 重要程度

for i in range(1, m + 1):
    a, b, c = map(int, input().split())
    a //= 10
    b *= a
    if c == 0:
        p[i][0] = a
        level[i][0] = b
    else:
        if p[c][1] == 0:
            p[c][1] = a
            level[c][1] = b
        else:
            p[c][2] = a
            level[c][2] = b

# 使用分组背包
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        a, b = p[i][0], level[i][0]
        c, d = p[i][1], level[i][1]
        e, f = p[i][2], level[i][2]
        dp[i][j] = dp[i - 1][j]
        if j >= a:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - a] + b)
        if j >= a + c:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - a - c] + b + d)
        if j >= a + e:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - a - e] + b + f)
        if j >= a + c + e:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - a - c - e] + b + d + f)

print(dp[m][n] * 10)