西安交大 軟件53 蔡少斐

題號：3_14

題目敘述：

某商店中每種商品都有一個價格。例如，一朵花的價格是2 ICU(ICU 是信息學競賽的貨幣的單位）;一個花瓶的價格是5 ICU。為了吸引更多的顧客，商店提供了特殊優惠價。

??? 特殊優惠商品是把一種或幾種商品分成一組。并降價銷售。例如:3朵花的價格不是6而是5 ICU ;2個花瓶加1朵花是10 ICU不是12 ICU。

??? 編一個程序，計算某個顧客所購商品應付的費用。要充分利用優惠價以使顧客付款最小。請注意，你不能變更顧客所購商品的種類及數量，即使增加某些商品會使付款總數減小也不允許你作出任何變更。假定各種商品價格用優惠價如上所述，并且某顧客購買物品為:3朵花和2個花瓶。那么顧客應付款為14ICU因為:

????????1朵花加2個花瓶: 優惠價:10? ICU

????????2朵花???????????正常價: 4?ICU

輸入數據

??? 用兩個文件表示輸入數據。第一個文件INPUT．TXT描述顧客所購物品（放在購物筐中）;第二個文件描述商店提供的優惠商品及價格（文件名為OFFER．TXT）。 兩個文件中都只用整數。

??? 第一個文件INPUT．TXT的格式為:第一行是一個數字B（0≤B≤5），表示所購商品種類數。下面共B行，每行中含3個數C，K，P。C 代表商品的編碼（每種商品有一個唯一的編碼），1≤C≤999。K代表該種商品購買總數，1≤K≤5。P 是該種商品的正常單價（每件商品的價格），1≤P≤999。請注意，購物筐中最多可放5*5＝25件商品。

第二個文件OFFER．TXT的格式為:第一行是一個數字S（0≤S≤99），表示共有S種優惠。下面共S行，每一行描述一種優惠商品的組合中商品的種類。下面接著是幾個數字對（C，K），其中C代表商品編碼，1≤C≤9 99。K代表該種商品在此組合中的數量，1≤K≤5。本行最后一個數字P（1≤P≤9999）代表此商品組合的優惠價。當然，優惠價要低于該組合中商品正常價之總和。

輸出數據

在輸出文件OUTPUT．TXT中寫一個數字（占一行）， 該數字表示顧客所購商品（輸入文件指明所購商品）應付的最低貨款。

題目解答：

本題應該采用動態規劃的方法進行設計，定義本題的最優子結構以及狀態為一個五元組：dp[x1][x2][x3][x4][x5]，其中x1代表要買的第一種物品的個數，x2代表要買的第二種物品的個數、以此類推。由于題目保證了B<=5，因此5元組絕對夠用。

我們用一個std::vector來存儲每套組合方案的捆綁的種類以及該種類需要購買的數量。

下面我們假定，不需要的物品一個都不能買，需要的物品也不能夠多買。

要列出該5元組的狀態轉移方程，其中優惠集合記為S。

.

在代碼實現的時候采用了備忘錄技術。

代碼表示：

#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> P; const int MAX = 6; const int INF = 1e9; int map[1000]; int n, m; int ids[MAX]; int price[MAX]; int nums[MAX]; vector<P> pairs[100]; int pP[100]; int pcnt = 0; int dp[MAX][MAX][MAX][MAX][MAX]; int times = 0; int dfs( int* x ) {times++;int r = dp[x[0]][x[1]][x[2]][x[3]][x[4]];if ( r > 0 ){return(r);}if ( x[0] == 0 && x[1] == 0 && x[2] == 0 && x[3] == 0 && x[4] == 0 ){return(0);}int minf = INF;for ( int i = 0; i < pcnt; i++ ){vector<P> & vec = pairs[i];int f = 1;int *y = new int[5];for ( int t = 0; t < 5; t++ )y[t] = 0;for ( auto p : vec ){int id = map[p.first];int num = p.second;if ( x[id] < num ){f = 0; break;}y[id] = -num;}if ( !f )continue;for ( int k = 0; k < 5; k++ )y[k] += x[k];minf = min( minf, pP[i] + dfs( y ) );}int s = 0;for ( int i = 0; i < 5; i++ ){s += x[i] * price[i];}minf = min( minf, s );return(dp[x[0]][x[1]][x[2]][x[3]][x[4]] = minf); }int main() {cin >> n;for ( int i = 0; i < n; i++ ){int C, K, PP;cin >> C >> K >> PP;ids[i] = C;nums[i] = K;price[i] = PP;if ( !map[C] ){map[C] = i;}}cin >> m;for ( int i = 0; i < m; i++ ){int k; cin >> k;vector<P> v;int f = 1;for ( int j = 0; j < k; j++ ){int a, b; cin >> a >> b;v.push_back( make_pair( a, b ) );}int PP;cin >> PP;if ( f ){pairs[pcnt] = v;pP[pcnt++] = PP;}}cout << "答案:" << dfs( nums ) << endl;cout << "運行次數:" << times << endl;return(0); }

運行結果：

總結

以上是生活随笔為你收集整理的最小费用购物问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。