??? 題目：http://www.nocow.cn/index.php/Translate:USACO/shopping

??? 題目很長，大致意思是買n種商品，然后這幾種商品按照不同的組合可以有不同的折扣，要我們按照最優的折扣來買東西。看到這道題很自然想到的是背包問題，但是這道題包含的信息明顯復雜的多。讓我想起了一句話“數據結構是算法的基礎，好的數據結構能夠很大程度上減少算法的復雜度。”

??? 我使用的第一種方法是，深度搜索剪枝方法，代碼如下：

#include <iostream> #include <fstream>#define TYPE 1000 #define SIZE 100using namespace std;struct Good {int id; int num; };struct GoodPrivilige {int num;Good g[5];int value; };//記錄商品價格 int value[TYPE] = {0}; GoodPrivilige p[SIZE]; int pl;Good need[5]; int nl;int result = 0x7FFFFFFF;void calResult(int level, int money) {if (level >= pl){for (int i=0;i <nl; i ++){money += need[i].num * value[need[i].id];}if (money < result){result = money;}}else{int n = 0;int m = money;while (true){ int flag = true;for (int i=0; i < nl; i ++){if (need[i].num < 0){flag = false;break;}}//檢驗是否有效//檢查有效性 并進行剪枝if(flag && m < result ){calResult(level+1,m);}elsebreak;n++;//使用方案的數量 for (int i=0; i < p[level].num; i ++){int id = p[level].g[i].id;for (int j=0; j < nl; j ++){if (id == need[j].id){need[j].num -= p[level].g[i].num;break;}//end if}//end for j}//end for im += p[level].value;}//end while//還原使用方案的數量 for (int i=0; i < p[level].num; i ++){int id = p[level].g[i].id;for (int j=0; j < nl; j ++){if (id == need[j].id){need[j].num += n * p[level].g[i].num;break;}//end if}//end for j}//end for i}//end else }int main() {ifstream fin("shopping.in");ofstream fout("shopping.out");//輸入數據//輸入方案fin >> pl;for (int i =0; i< pl; i ++){fin >> p[i].num;for (int j=0; j < p[i].num; j ++){fin >> p[i].g[j].id;fin >> p[i].g[j].num;}fin >> p[i].value;}//輸入要購買的物品fin >> nl;for (int i=0; i < nl; i ++){fin >> need[i].id >> need[i].num;fin >> value[need[i].id];}calResult(0,0);fout << result << endl;return 0; }

??? 很可惜的是在Test10的時候，就超時了。

Executing...Test 1: TEST OK [0.000 secs, 3024 KB]Test 2: TEST OK [0.011 secs, 3024 KB]Test 3: TEST OK [0.011 secs, 3024 KB]Test 4: TEST OK [0.000 secs, 3024 KB]Test 5: TEST OK [0.000 secs, 3024 KB]Test 6: TEST OK [0.022 secs, 3024 KB]Test 7: TEST OK [0.022 secs, 3024 KB]Test 8: TEST OK [0.011 secs, 3024 KB]Test 9: TEST OK [0.011 secs, 3024 KB]> Run 10: Execution error: Your program (`shopping') used more thanthe allotted runtime of 1 seconds (it ended or was stopped at1.674 seconds) when presented with test case 10. It used 3024 KBof memory.

??? 沒辦法，只好對其進行優化，跟背包的改進算法是一樣的，只是用到了一個5維的數組，用于記錄迭代前進的過程。代碼如下：

#include <iostream> #include <fstream>#define TYPE 1000 #define SIZE 100using namespace std;struct Good {int id; int num; };struct GoodPrivilige {int num;Good g[5];int value; };//記錄商品價格 int value[TYPE] = {0}; GoodPrivilige p[SIZE]; int pl;Good need[5]; int nl;int result; int table[6][6][6][6][6] = {0};int getPrivilige(int index,int id) {for (int i=0; i < p[index].num; i ++){if (id == p[index].g[i].id){return p[index].g[i].num;}}return 0; }void calResult() {for (int n = 0; n < pl; n ++){int p1 = getPrivilige(n, need[0].id);int p2 = getPrivilige(n, need[1].id);int p3 = getPrivilige(n, need[2].id);int p4 = getPrivilige(n,need[3].id);int p5 = getPrivilige(n,need[4].id);for (int i=p1; i <= need[0].num; i ++){for (int j=p2; j <= need[1].num; j ++){for (int k=p3; k <= need[2].num; k ++){for (int l =p4; l <= need[3].num; l ++){for (int m = p5; m <= need[4].num; m ++){if(table[i][j][k][l][m] > table[i-p1][j-p2][k-p3][l-p4][m-p5] + p[n].value){table[i][j][k][l][m] = table[i-p1][j-p2][k-p3][l-p4][m-p5] + p[n].value;}}//end m}//end l}//end k}//end j}//end i}//end n; }int main() {ifstream fin("shopping.in");ofstream fout("shopping.out");//輸入數據//輸入方案fin >> pl;for (int i =0; i< pl; i ++){fin >> p[i].num;for (int j=0; j < p[i].num; j ++){fin >> p[i].g[j].id;fin >> p[i].g[j].num;}fin >> p[i].value;}//輸入要購買的物品fin >> nl;for (int i=0; i < nl; i ++){fin >> need[i].id >> need[i].num;fin >> value[need[i].id];}//初始化for (int i=0; i <= need[0].num; i ++){for (int j=0; j <= need[1].num; j ++){for (int k=0; k <= need[2].num; k ++){for (int l =0; l <= need[3].num; l ++){for (int m = 0; m <= need[4].num; m ++){table[i][j][k][l][m] = i * value[need[0].id] + j * value[need[1].id] + k * value[need[2].id] + l * value[need[3].id] + m * value[need[4].id];}//end m}//end l}//end k}//end j}//end icalResult();result = table[need[0].num][need[1].num][need[2].num][need[3].num][need[4].num];fout << result << endl;return 0; }

??? 速度還不錯。結果如下：

Executing...Test 1: TEST OK [0.022 secs, 3052 KB]Test 2: TEST OK [0.000 secs, 3052 KB]Test 3: TEST OK [0.000 secs, 3052 KB]Test 4: TEST OK [0.000 secs, 3052 KB]Test 5: TEST OK [0.011 secs, 3052 KB]Test 6: TEST OK [0.000 secs, 3052 KB]Test 7: TEST OK [0.000 secs, 3052 KB]Test 8: TEST OK [0.000 secs, 3052 KB]Test 9: TEST OK [0.011 secs, 3052 KB]Test 10: TEST OK [0.000 secs, 3052 KB]Test 11: TEST OK [0.011 secs, 3052 KB]Test 12: TEST OK [0.000 secs, 3052 KB]All tests OK.

總結

以上是生活随笔為你收集整理的USACO算法系列十五——shoping的全部內容，希望文章能夠幫你解決所遇到的問題。

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