最多有5种商品，把每一种优惠，把他们看成分别有5个权重（w1,w2,w3,w4,w5），一种价值cost的背包。
另外也把原价购买一件商品作为一种背包，例如（w1=1，w2..5=0）cost=3
/**//*
ID: lorelei3
TASK: shopping
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAX = 100;
const int INF = 999999999;
typedef struct
{
int w[6];
int cost;
}Offer;
Offer offers[100];
int a[6], hash[10];
int s,m,t,c,k,p,n,b;
int v1,v2,v3,v4,v5;
int f[6][6][6][6][6];
inline int decode(int code){
int i;
for(i=1; i<=t; ++i)
if(hash[i]==code)
return i;
hash[++t] = code;
return t;
}
int main(){
int i,j;
ifstream fin("shopping.in");
ofstream fout("shopping.out");
fin>>s;
for(i=0; i<s; ++i){
++m;
fin>>n;
for(j=0; j<n; ++j){
fin>>c>>k;
offers[m].w[decode(c)] = k;
}
fin>>offers[m].cost;
}
fin>>b;
for(v1=0; v1<6; ++v1)
for(v2=0; v2<6; ++v2)
for(v3=0; v3<6; ++v3)
for(v4=0; v4<6; ++v4)
for(v5=0; v5<6; ++v5)
f[v1][v2][v3][v4][v5]=INF;
f[0][0][0][0][0] = 0 ;
for(i=0; i<b; ++i){
fin>>c>>k>>p;
++m;
int code = decode(c);
offers[m].w[code] = 1;
offers[m].cost = p;
a[code] = k;
}
for(i=1; i<=m; ++i)
for(v1=offers[i].w[1]; v1<=5; ++v1)
for(v2=offers[i].w[2]; v2<=5; ++v2)
for(v3=offers[i].w[3]; v3<=5; ++v3)
for(v4=offers[i].w[4]; v4<=5; ++v4)
for(v5=offers[i].w[5]; v5<=5; ++v5)
if(f[v1][v2][v3][v4][v5] > f[v1-offers[i].w[1]][v2-offers[i].w[2]][v3-offers[i].w[3]][v4-offers[i].w[4]][v5-offers[i].w[5]] + offers[i].cost )
f[v1][v2][v3][v4][v5] = f[v1-offers[i].w[1]][v2-offers[i].w[2]][v3-offers[i].w[3]][v4-offers[i].w[4]][v5-offers[i].w[5]] + offers[i].cost;
fout<<f[a[1]][a[2]][a[3]][a[4]][a[5]]<<endl;
return 0;
}
PS:最近忙着写标书，真是廉价劳动力哇。。
posted on 2011-01-10 21:26
小阮 阅读(289)
评论(0) 编辑 收藏 引用 所属分类:
USACO