題目：
你在一間速食店點餐，店裡有N種餐點(N<=6)
而店裡現在推出K種套餐(K<=8)，由他們的N種餐點組合而成
想當然耳，套餐的價格會比單點其中所有餐點的總和來的便宜
給你所有餐點價格，與套餐的內容、價格
然後Q次點餐(Q<=10)，求搭配出點餐需求的最小花費，點餐中個餐點數量皆<=9
注意，為了避免浪費，食物不能多，要恰好滿足需求！
表示方式
例如有3種餐點，套餐內容的表示方式為(a, b, c, price)，某餐點數量可以是0
做法：
說了這麼多，就是個物品可無限次拿取的背包問題
物品共有6個單點與8個套餐最多14個
令dp[i][j] = 前i個物品中湊得j組合的最小花費
然而組合最多也就6種，每種數量最多9個
於是可以開dp[15][10][10][10][10][10][10]
要拿或不拿，寫出轉移式
dp[i][DM[1]][DM[2]][DM[3]][DM[4]][DM[5]][DM[6]] =
min( dp[i][DM[1]-CB[1]][..][..][..][..][..]+PR[i], dp[i-1][DM[1]][..][..][..][..][..] );
DM: demand, 這筆order的各個餐點需求數量
CB: combo, 14個搭配方式的各個餐點數量
PR: price, 價錢
用top-down或bottom-up都可以，複雜度不會高於O(15*10^6)
code:
沒有留言:
張貼留言