一道DP题，DP的方程很简单:
f[a][b][c][d][e] = min(f[a][b][c][d][e], f[a – cost[0][0]][b – cost[0][1]][c – cost[0][2]][d – cost[0][3]][e – cost[0][4]], f[a – cost[1][0]][b – cost[1][1]][c – cost[1][2]][d – cost[1][3]][e – cost[1][4]]…);
代码如下：
/
LANG: C
ID: zqynux2
PROG: shopping
/
#include <stdio.h>
#define min(a, b) ((a)<(b)?(a):(b))
struct you{
int len;
struct thing{
int id, num;
}buy[5];
int priece;
}buy[99];
int money[6];
int num[6];
int good[1000];
int f[6][6][6][6][6];
int n, m;
int s[6];
void init(int now)
{
int i;
if(now == m){
for(i = 0; i < m; i++){
f[s[0]][s[1]][s[2]][s[3]][s[4]] += money[i + 1] s[i];
}
return;
}
for(i = 0; i <= 5; i++){
s[now] = i;
init(now + 1);
}
}
void deal(int now)
{
int used[6];
int i;
memset(used, 0, sizeof(used));
for(i = 0; i < buy[now].len; i++){
used[good[buy[now].buy[i].id]] += buy[now].buy[i].num;
}
if(used[0] != 0){
return;
}
for(i = 0; i < 5; i++){
if(used[i + 1] > s[i]){
return;
}
}
f[s[0]][s[1]][s[2]][s[3]][s[4]] = min(f[s[0]][s[1]][s[2]][s[3]][s[4]],
f[s[0] – used[1]][s[1] – used[2]][s[2] – used[3]][s[3] – used[4]][s[4] – used[5]]
+ buy[now].priece);
}
void srch(int now)
{
int i;
if(now == m){
for(i = 0; i < n; i++){
deal(i);
}
return;
}
for(i = 0; i <= 5; i++){
s[now] = i;
srch(now + 1);
//写成了init
}
}
int main(void)
{
int i, j;
freopen("shopping.in", "r", stdin);
freopen("shopping.out", "w", stdout);
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &buy[i].len);
for(j = 0; j < buy[i].len; j++){
scanf("%d%d", &buy[i].buy[j].id,
&buy[i].buy[j].num);
}
scanf("%d", &buy[i].priece);
}
scanf("%d", &m);
for(i = 1; i <= m; i++){
scanf("%d%d%d", &j, &num[i], &money[i]);
good[j] = i;
}
init(0); / 将价格进行初始化 /
srch(0); / DP */
printf("%d\n", f[num[1]][num[2]][num[3]][num[4]][num[5]]);
return 0;
}