2018年4月6日

UVa10898 Combo Deal

連假快樂,寫個DP好過節

這次連放了五天呢,禮拜一二模擬考也閒著,估計都會在打code吧!


題目:

你在一間速食店點餐,店裡有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:
#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;
}


沒有留言:

張貼留言