※ 引述《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背包詳細的部分我再想怎麼寫