※ 引述《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背包詳細的部分我再想怎麼寫 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723776192.A.8DC.html