背包問題，dp解決。
dp[i][j][k][m][n]表示第0-4種物品分別購買i-n個(gè)時(shí)，所需的最小費(fèi)用。
那么對(duì)于每一個(gè)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中提出用最短路徑的方法來解，思路很巧妙。把”裝有不同種數(shù)和數(shù)量的物品“的籃子看作結(jié)點(diǎn)，把offer作為邊(把購買一件物品的原始價(jià)格看成一種退化的offer)，把價(jià)格作為邊長(zhǎng)度。這樣就轉(zhuǎn)換成從籃子(0,0,0,0,0)到所求結(jié)點(diǎn)的最短路徑問題。
代碼如下:
#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到”按物品出現(xiàn)順序所給的編號(hào)“的映射
int?price[1000];//product id對(duì)應(yīng)的物品價(jià)格
int?product_num;//物品總數(shù)目
int?products[5];//存放product id
int?amount[5];//product 所需的數(shù)量
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;
????}
??? //沒有折扣時(shí)的價(jià)格
????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;
}
上面代碼有個(gè)嚴(yán)重的bug，謝謝網(wǎng)友“我也湊熱鬧"指出。由于map所有值都為0。所以未在商品列表中出現(xiàn)的商品的map值都為0，即都映射為第一個(gè)商品。現(xiàn)改成將map初始化為-1，并增加判斷語句。此外將初始化dp的語句合并到后面，以簡(jiǎn)化代碼。
#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;
}