背包問題，dp解決。
dp[i][j][k][m][n]表示第0-4種物品分別購買i-n個時，所需的最小費用。
那么對于每一個offer
dp[i][j][k][m][n] = min ( dp[i][j][k][m][n], dp[i-o[0]][j-o[1]][k-o[2]][m-o[3]][n-o[4]]+offer.cost);
analysis中提出用最短路徑的方法來解，思路很巧妙。把”裝有不同種數和數量的物品“的籃子看作結點，把offer作為邊(把購買一件物品的原始價格看成一種退化的offer)，把價格作為邊長度。這樣就轉換成從籃子(0,0,0,0,0)到所求結點的最短路徑問題。
代碼如下:
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("shopping.in");
ofstream?fout("shopping.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?dp[6][6][6][6][6];
struct?offer{
????int?pro_num;
????int?price;
????int?product[5];
????int?amount[5];
};
int?offer_num;
offer?offers[100];
int?map[1000]; //product id到”按物品出現順序所給的編號“的映射
int?price[1000];//product id對應的物品價格
int?product_num;//物品總數目
int?products[5];//存放product id
int?amount[5];//product 所需的數量
void?solve()
{
????in>>offer_num;
????for(int?i=0;i<offer_num;++i){
????????in>>offers[i].pro_num;
????????for(int?j=0;j<offers[i].pro_num;++j){
????????????in>>offers[i].product[j]>>offers[i].amount[j];
????????}
????????in>>offers[i].price;
????}
????
????int?pro_idx?=?0;
????in>>product_num;
????for(int?i=0;i<product_num;++i){
????????in>>products[i];
????????in>>amount[i];
????????in>>price[i];
????????map[?products[i]?]?=?i;
????}
??? //沒有折扣時的價格
????for(int?i=0;i<=5;++i)
????????for(int?j=0;j<=5;++j)
????????????for(int?k=0;k<=5;++k)
????????????????for(int?m=0;m<=5;++m)
????????????????????for(int?n=0;n<=5;++n){
????????????????????????dp[i][j][k][m][n]?=?
????????????????????????????price[0]*i+
????????????????????????????price[1]*j+
????????????????????????????price[2]*k+
????????????????????????????price[3]*m+
????????????????????????????price[4]*n;
????????????????????}
????for(int?i=0;i<=5;++i)
????????for(int?j=0;j<=5;++j)
????????????for(int?k=0;k<=5;++k)
????????????????for(int?m=0;m<=5;++m)
????????????????????for(int?n=0;n<=5;++n){
????????????????????????int?tmp[5];
????????????????????????for(int?s=0;s<offer_num;++s){
????????????????????????????memset(tmp,0,sizeof(tmp));????
????????????????????????????for(int?t=0;t<offers[s].pro_num;++t){
????????????????????????????????tmp[map[offers[s].product[t]]]?=?offers[s].amount[t];
????????????????????????????}
????????????????????????????if(i>=tmp[0]&&j>=tmp[1]&&k>=tmp[2]&&m>=tmp[3]&&n>=tmp[4]){
????????????????????????????????dp[i][j][k][m][n]?=?min(?dp[i][j][k][m][n],
????????????????????????????????????????dp[i-tmp[0]][j-tmp[1]][k-tmp[2]][m-tmp[3]][n-tmp[4]]+
????????????????????????????????????????offers[s].price);
????????????????????????????}
????????????????????????}
????????????????????}
????out<<dp[amount[0]][amount[1]][amount[2]][amount[3]][amount[4]]<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
上面代碼有個嚴重的bug，謝謝網友“我也湊熱鬧"指出。由于map所有值都為0。所以未在商品列表中出現的商品的map值都為0，即都映射為第一個商品。現改成將map初始化為-1，并增加判斷語句。此外將初始化dp的語句合并到后面，以簡化代碼。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("shopping.in");
ofstream?fout("shopping.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?dp[6][6][6][6][6];
struct?offer{
????int?pro_num;
????int?price;
????int?product[5];
????int?amount[5];
};
int?offer_num;
offer?offers[100];
int?map[1000];
int?price[1000];
int?product_num;
int?products[5];
int?amount[5];
void?solve()
{
????in>>offer_num;
????for(int?i=0;i<offer_num;++i){
????????in>>offers[i].pro_num;
????????for(int?j=0;j<offers[i].pro_num;++j){
????????????in>>offers[i].product[j]>>offers[i].amount[j];
????????}
????????in>>offers[i].price;
????}
????
????int?pro_idx?=?0;
????in>>product_num;
????//2009.07.27修改
????memset(map,-1,sizeof(map));
????for(int?i=0;i<product_num;++i){
????????in>>products[i];
????????in>>amount[i];
????????in>>price[i];
????????map[?products[i]?]?=?i;
????}
????for(int?i=0;i<=5;++i)
????????for(int?j=0;j<=5;++j)
????????????for(int?k=0;k<=5;++k)
????????????????for(int?m=0;m<=5;++m)
????????????????????for(int?n=0;n<=5;++n){
?????????????????????????dp[i][j][k][m][n]?=?
????????????????????????????price[0]*i+
????????????????????????????price[1]*j+
????????????????????????????price[2]*k+
????????????????????????????price[3]*m+
????????????????????????????price[4]*n;
????????????????????????int?tmp[5];
????????????????????????for(int?s=0;s<offer_num;++s){
????????????????????????????memset(tmp,0,sizeof(tmp));????
????????????????????????????for(int?t=0;t<offers[s].pro_num;++t){
????????????????????????????????//2009.07.27修改
????????????????????????????????if(?map[offers[s].product[t]]!=-1)
????????????????????????????????????tmp[map[offers[s].product[t]]]?=?offers[s].amount[t];
????????????????????????????}
????????????????????????????if(i>=tmp[0]&&j>=tmp[1]&&k>=tmp[2]&&m>=tmp[3]&&n>=tmp[4]){
????????????????????????????????dp[i][j][k][m][n]?=?min(?dp[i][j][k][m][n],
????????????????????????????????????????dp[i-tmp[0]][j-tmp[1]][k-tmp[2]][m-tmp[3]][n-tmp[4]]+
????????????????????????????????????????offers[s].price);
????????????????????????????}
????????????????????????}
????????????????????}
????out<<dp[amount[0]][amount[1]][amount[2]][amount[3]][amount[4]]<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}