2022-05-31：某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有

2022-05-31：某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有X元的预算。 该平台上所有的 n 个游戏均有折扣，标号为 i 的游戏的原价a_i元，现价只要b_i元， 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为 w_i， 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算， 只要满足 : 获得的总优惠金额不低于超过预算的总金额， 那在心理上就不会觉得吃亏。 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。 来自字节内部训练营。 来自力扣bytedance-006. 夏季特惠。

答案2022-05-31：

转化之后是背包问题。

代码用rust编写。代码如下：

fn main() {
    let sc: Vec<isize> = vec![4, 100, 100, 73, 60, 100, 89, 35, 30, 21, 30, 10, 8, 10];
    let mut ii: isize = 0;
    while ii < sc.len() as isize {
        let n = sc[ii as usize];
        ii += 1;
        let mut money = sc[ii as usize];
        ii += 1;
        let mut costs: Vec<isize> = vec![];
        for _i in 0..n {
            costs.push(0);
        }
        let mut values: Vec<isize> = vec![];
        for _i in 0..n {
            values.push(0);
        }
        let mut size: isize = 0;
        let mut ans: isize = 0;
        for _i in 0..n {
            // 打折前
            let pre = sc[ii as usize];
            ii += 1;
            // 打折后
            let pos = sc[ii as usize];
            ii += 1;
            // 满足度
            let happy = sc[ii as usize];
            ii += 1;
            // 节省的钱(save) = 打折前(pre) - 打折后(pos)
            let save = pre - pos;
            // 带来的好处(well) = 节省的钱 - 打折后(pos)
            let well = save - pos;
            // 比如，一件"一定要买的商品":
            // 预算 = 100，商品原价 = 10，打折后 = 3
            // 那么好处 = (10 - 3) - 3 = 4
            // 所以，这件商品把预算增加到了104，一定要买
            // 接下来，比如一件"需要考虑的商品"，预算 = 104，商品原价 = 10，打折后 = 8
            // 那么好处 = (10 - 8) - 8 = -6
            // 这件商品，就花掉6元！
            // 也就是说，以后花的不是打折后的值，是"坏处"
            let cost = -well;
            if well >= 0 {
                money += well;
                ans += happy;
            } else {
                costs[size as usize] = cost;
                values[size as usize] = happy;
                size += 1;
            }
        }
        let mut dp: Vec<Vec<isize>> = vec![];
        for i in 0..size + 1 {
            dp.push(vec![]);
            for _j in 0..money + 1 {
                dp[i as usize].push(0);
            }
        }
        for a in 0..=size {
            for b in 0..=money {
                dp[a as usize][b as usize] = -2;
            }
        }
        ans += process(&mut costs, &mut values, size, 0, money, &mut dp);
        println!("{}", ans);
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn process(
    costs: &mut Vec<isize>,
    values: &mut Vec<isize>,
    size: isize,
    i: isize,
    money: isize,
    dp: &mut Vec<Vec<isize>>,
) -> isize {
    if money < 0 {
        return -1;
    }
    if i == size {
        return 0;
    }
    if dp[i as usize][money as usize] != -2 {
        return dp[i as usize][money as usize];
    }
    let p1 = process(costs, values, size, i + 1, money, dp);
    let mut p2 = -1;
    let next = process(costs, values, size, i + 1, money - costs[i as usize], dp);
    if next != -1 {
        p2 = values[i as usize] + next;
    }
    let ans = get_max(p1, p2);
    dp[i as usize][money as usize] = ans;
    return ans;
}

执行结果如下：

左神java代码

bytedance-006. 夏季特惠