# USACO-Section3.3 Shopping Offers【完全背包】

xiaoxiao2021-02-28  17

## OUTPUT FORMAT：

SAMPLE INPUT

2 1 7 3 5 2 7 1 8 2 10 2 7 3 2 8 2 5

SAMPLE OUTPUT

14

## 解题思路：

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> #define INF 99999999 using namespace std; FILE *fin,*fout; typedef struct discount{ int cost;//记录优惠价 int c[1000];//记录编号 }Dis; typedef struct goods{ int c;//记录编号 int cost;//记录优惠价 }Goods; int s,n,b; Dis discount[100]; Goods g[5]; int dp[6][6][6][6][6]; int c[5];//记录商品的个数，可以放在Goods里面 void init(){ int flag=5; for(int i=0;i<=c[0];i++){ for(int j=0;j<=c[1];j++){ for(int k=0;k<=c[2];k++){ for(int l=0;l<=c[3];l++){ for(int m=0;m<=c[4];m++){ dp[i][j][k][l][m]=i*g[0].cost+j*g[1].cost+k*g[2].cost+l*g[3].cost+m*g[4].cost; } } } } } } void fun(){ init(); int m[5]; for(int temp=0;temp<s;temp++){ int m0=discount[temp].c[g[0].c]; int m1=discount[temp].c[g[1].c]; int m2=discount[temp].c[g[2].c]; int m3=discount[temp].c[g[3].c]; int m4=discount[temp].c[g[4].c]; int tempcost=discount[temp].cost; for(int i=m0;i<=c[0];i++){ for(int j=m1;j<=c[1];j++){ for(int k=m2;k<=c[2];k++){ for(int l=m3;l<=c[3];l++){ for(int m=m4;m<=c[4];m++){ dp[i][j][k][l][m]=min(dp[i][j][k][l][m],dp[i-m0][j-m1][k-m2][l-m3][m-m4]+tempcost); } } } } } } } int main(){ fin = fopen ("shopping.in", "r"); fout = fopen ("shopping.out", "w"); fscanf(fin,"%d",&s); for(int i=0;i<s;i++){ fscanf(fin,"%d",&n); int a,b; for(int j=0;j<n;j++){ fscanf(fin,"%d%d",&a,&b); discount[i].c[a]=b; } fscanf(fin,"%d",&discount[i].cost); } fscanf(fin,"%d",&b); for(int i=0;i<b;i++){ fscanf(fin,"%d%d%d",&g[i].c,&c[i],&g[i].cost); } fun(); fprintf(fout,"%d\n",dp[c[0]][c[1]][c[2]][c[3]][c[4]]); exit(0); }