背包问题，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;
}