※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 【观念】0-1背包问题
: 每种物品只有一个且不可分割，只能选择拿或不拿。每种物品的价值为 v，重量为 w。
: 在背包负重有限的情况下，求背包能够容纳的物品的最大价值。
: 感觉可以写一个DP阵列来解肯德基的优惠券组合问题
: 在固定金额或最多优惠的情况取得目标(像是一定要两块炸鸡)的排列
: 不然每次慢慢组合优惠券好累==
不过肯德基优惠码跟传统0-1背包比较不一样
他是N个物品放在一起并标示成W价值
所以要先有一个管理优惠码的数据库
取得的部分另外做 可以爬虫也可以手动key
然后让取得的部分能输入优惠码
我用ChatGPT产生的Prototype:
use std::collections::HashSet;
#[derive(Debug)]
struct Coupon { // 优惠码物件
items: HashSet<&'static str>, // 包含类似"burger"
cost: usize, // 价格
code: &'static str, // 优惠码代号
}
struct CouponController {
coupons: Vec<Coupon>,
}
impl CouponController {
fn new() -> Self {
CouponController {
coupons: Vec::new(),
}
}
fn add_coupon(&mut self, items: HashSet<&'static str>,
cost: usize, code: &'static str) {
let coupon = Coupon { items, cost, code };
self.coupons.push(coupon);
}
fn get_coupons(&self) -> &Vec<Coupon> {
&self.coupons
}
}
使用参考:
let mut controller = CouponController::new();
controller.add_coupon(["Burger"].iter().cloned().collect(), 5, "CODE1");
controller.add_coupon(["Fries", "Cola"]
.iter().cloned().collect(), 6, "CODE2");
controller.add_coupon(["Burger", "Cola"]
.iter().cloned().collect(), 8, "CODE3");
使用0-1背包的部分是这样:
// 需求 比如我要汉堡+薯条+可乐
let required_items: HashSet<&str> = ["Burger", "Fries", "Cola"]
.iter().cloned().collect();
// 最高能接受的花费
let budget = 15;
match knapsack(controller.get_coupons(), &required_items, budget) {
Some(min_cost) => println!("达成所有需求的最低成本: {}", min_cost),
None => println!("无法在预算内达成所有需求"),
}
0-1背包详细的部分我再想怎么写