题解 | #购物单#

import Foundation

var i = 0
var N = 0
var m = 0
var masterArr = [(sn:Int, price:Int, manyi:Int)]()
var dict = [Int : [(price:Int, manyi:Int)]]()
while let line = readLine() {
    let parts = line.split(separator: " ")
    if (parts[0] == "***") {
        break
    }
    if (i == 0) {
        N = Int(parts[0])!
        m = Int(parts[1])!
    } else if (Int(parts[2])! == 0) { // 主件
         masterArr.append((sn:i - 1, price:Int(parts[0])!, manyi:Int(parts[1])!))
    } else {
        var fujian:[(price:Int, manyi:Int)] = dict[Int(parts[2])! - 1] ?? []
        fujian.append((price:Int(parts[0])!, manyi:Int(parts[1])!))
        dict[Int(parts[2])! - 1] = fujian
    }
    i = i + 1
}

//print(N)
//print(m)
//print(masterArr)
//print(dict)
var amount = masterArr.count
var total = N
var dp:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: total + 1), count: amount + 1)

func calulate(total:Int, amount:Int) {
    // i 前i个，total:最大的钱数[0, tatal]， dp：最大的满意度
    for i in 0 ... amount {
        for j in 0 ... total {
            if ( i == 0) {
                dp[0][j] = 0
                continue
            }
            if (j == 0) {
                dp[i][0] = 0
                continue
            }
            var maxVal = 0
            // 是否选择第i个 选择，不选择
            // 不选择
            dp[i][j] = dp[i - 1][j]
            maxVal = max(dp[i][j], maxVal)
            
            // 选择主件和附件,前i个，对应的下标就是 i - 1
            var master = masterArr[i - 1]
            var fujians = dict[master.sn] ?? []
            
            // 选择 有多种情况

            // 只选主件、 选主件和附件1、选主件和附件2、选主件和附件1和2
            if j - master.price >= 0 {
                    dp[i][j] = dp[i - 1][j - master.price] + master.price * master.manyi
                    maxVal = max(dp[i][j], maxVal)
            }

            if fujians.count == 1 {
                 // 主件 + 附件1
                var fujian1 = fujians[0]
                if (j - master.price - fujian1.price >= 0) {
                    dp[i][j] = dp[i - 1][j - master.price - fujian1.price] + master.price * master.manyi + fujian1.price * fujian1.manyi
                    maxVal = max(dp[i][j], maxVal)
                }
                
            } else if fujians.count == 2 {
                var fujian1 = fujians[0]
                var fujian2 = fujians[1]
                
                // 主件 + 附件1
                if (j - master.price - fujian1.price >= 0) {
                    dp[i][j] = dp[i - 1][j - master.price - fujian1.price] + master.price * master.manyi + fujian1.price * fujian1.manyi
                    maxVal = max(dp[i][j], maxVal)
                }
                
                
                // 主件 + 附件2
                if (j - master.price - fujian2.price >= 0) {
                    dp[i][j] = dp[i - 1][j - master.price - fujian2.price] + master.price * master.manyi + fujian2.price * fujian2.manyi
                    maxVal = max(dp[i][j], maxVal)
                }
                
                
                // 主件 + 附件1 + 附件2
                if (j - master.price - fujian1.price - fujian2.price >= 0) {
                    dp[i][j] = dp[i - 1][j - master.price - fujian1.price - fujian2.price] + master.price * master.manyi + fujian1.price * fujian1.manyi + fujian2.price * fujian2.manyi
                    maxVal = max(dp[i][j], maxVal)
                }
            }
            dp[i][j] = maxVal
        }
    }
}

calulate(total: total, amount: amount)
print(dp[amount][total])