題目:
你在一間速食店點餐,店裡有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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string.h> | |
using namespace std; | |
int N, K, Q, PR[15], CB[15][10], order[10], dp[15][10][10][10][10][10][10]; | |
int dfs(int index, int DM[]) { // top down | |
if ( index == 0 ) { | |
for ( int i=1; i<=6; ++i ) | |
if ( DM[i] != 0 ) // illegal | |
return 1e9; | |
return 0; // legal | |
} | |
if ( dp[index][DM[1]][DM[2]][DM[3]][DM[4]][DM[5]][DM[6]] != 0 ) | |
return dp[index][DM[1]][DM[2]][DM[3]][DM[4]][DM[5]][DM[6]]; | |
int pick[7] = {0,0,0,0,0,0,0}; | |
for ( int i=1; i<=6; ++i ) { | |
pick[i] = DM[i] - CB[index][i]; | |
if ( pick[i] < 0 ) // illegal one | |
return dp[index][DM[1]][DM[2]][DM[3]][DM[4]][DM[5]][DM[6]] = dfs(index-1,DM); | |
} | |
return dp[index][DM[1]][DM[2]][DM[3]][DM[4]][DM[5]][DM[6]] = | |
min(dfs(index,pick)+PR[index], dfs(index-1,DM)); // legal, to pick or not to pick | |
} | |
int main() { | |
ios::sync_with_stdio(0); | |
cin.tie(0); | |
while ( cin >> N ) { | |
memset(CB,0,sizeof(CB)); | |
memset(PR,0,sizeof(PR)); | |
memset(dp,0,sizeof(dp)); // set 0 as unused | |
for ( int i=1; i<=N; ++i ) { | |
CB[i][i] = 1; | |
cin >> PR[i]; | |
dp[i][i==1][i==2][i==3][i==4][i==5][i==6] = PR[i]; | |
} | |
cin >> K; | |
for ( int i=1; i<=K; ++i ){ | |
for ( int j=1; j<=N; ++j ) cin >> CB[N+i][j]; | |
cin >> PR[N+i]; | |
dp[i][CB[N+i][1]][CB[N+i][2]][CB[N+i][3]][CB[N+i][4]][CB[N+i][5]][CB[N+i][6]] = PR[N+i]; | |
} | |
cin >> Q; | |
while ( Q-- ) { | |
for ( int i=1; i<=N; ++i ) cin >> order[i]; | |
cout << dfs(N+K,order) << '\n'; | |
} | |
} | |
return 0; | |
} |
沒有留言:
張貼留言