Gift Hunting 解决的思路

Question

Problem Description
After winning two coupons for the largest shopping mart in your city, you can't wait inviting your girlfriend for gift hunting. Having inspected hundreds of kinds of souvenirs, toys and cosmetics, you finally narrowed down the candidate list to only n gifts, numbered 1 to n. Each gift has a happiness value that measures how happy your girlfriend would be, if you get this gift for her. Some of them are special - you must get it for your girlfriend (note that whether a gift is special has nothing to do with its happiness value).

Coupon 1 can be used to buy gifts with total price not greater than V1 (RMB). Like most other coupons, you can’t get any money back if the total price is strictly smaller than V1. Coupon 2 is almost the same, except that it’s worth V2. Coupons should be used separately. That means you cannot combine them into a super-coupon that’s worth V1+V2. You have to divide the gifts you choose into two part, one uses coupon 1, the other uses coupon 2.

It is your girlfriend's birthday today. According to the rules of the mart, she can take one (only one) gift for FREE! Here comes your challenge: how to make your girlfriend as happy as possible?

Input
There will be at most 20 test cases. Each case begins with 3 integers V1, V2 and n (1 <= V1 <= 500, 1 <= V2 <= 50, 1 <= n <= 300), the values of coupon 1 and coupon 2 respectively, and the number of candidate gifts. Each of the following n lines describes a gift with 3 integers: P, H and S, where P is the price, H is the happiness (1 <= P,H <= 1000), S=1 if and only if this is a special gift - you must buy it (or get it for free). Otherwise S=0. The last test case is followed by V1 = V2 = n = 0, which should not be processed.

Output
For each test case, print the case number and the maximal total happiness of your girlfriend. If you can't finish the task, i.e. you are not able to buy all special gifts even with the 1-FREE bonus, the happiness is -1 (negative happiness means she's unhappy). Print a blank line after the output of each test case.

Sample Input
3 2 4
3 10 1
2 10 0
5 100 0
5 80 0
3 2 4
3 10 1
2 10 0
5 100 0
5 80 1
0 0 0

Sample Output
Case 1: 120

Case 2: 100

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 导入必要的库
library(Rcpp)
library(ggplot2)

# 定义函数计算总幸福值
calculate_happiness <- function(V1, V2, n, gifts) {
  # 初始化最大幸福值为0
  max_happiness <- 0
  
  # 遍历所有礼物
  for (i in 1:n) {
    # 计算当前礼物的价格和满意度
    price <- gifts[i, "P"]
    happiness <- gifts[i, "H"]
    
    # 如果是特殊礼物，则直接添加到最大幸福值中
    if (happiness == 1) {
      max_happiness <- max(max_happiness, price + V1)
    }
    # 否则，如果价格小于等于V1，则直接添加到最大幸福值中
    else if (price <= V1) {
      max_happiness <- max(max_happiness, price + V1)
    } else {
      # 否则，从V2开始减价购买，直到价格小于等于V1为止
      while (price > V1 && price > 0) {
        price <- price - V2
      }
      max_happiness <- max(max_happiness, price + V1)
    }
  }
  
  return(max_happiness)
}

# 主程序
n_cases <- readline()
while (n_cases != "") {
  # 分别读取每个测试案例的数据
  V1 <- as.integer(readline())
  V2 <- as.integer(readline())
  n <- as.integer(readline())
  
  # 生成随机数据
  gifts <- matrix(0, nrow = n, ncol = 3)
  prices <- sample(1:1000, n, replace = TRUE)
  h = sample(c(0, 1), n, replace = TRUE)
  for (i in 1:n) {
    gifts[i, ] <- c(prices[i], h[i])
  }
  
  # 调用函数计算最大幸福值
  max_happiness <- calculate_happiness(V1, V2, n, gifts)
  
  # 输出结果
  if (max_happiness >= 0) {
    cat("Case ", n_cases, ": ", max_happiness, "\n")
  } else {
    cat("Case ", n_cases, ": -1\n")
  }
  
  n_cases <- readline()
}