某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有X元的预算。
该平台上所有的 n 个游戏均有折扣，标号为 i 的游戏的原价a_i元，现价只要b_i元，
也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为 w_i，
由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算，
只要满足 : 获得的总优惠金额不低于超过预算的总金额，
那在心理上就不会觉得吃亏。
现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
转化之后是背包问题。
代码用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;
}执行结果如下：
