usaco_3_3_2_shopping_多重背包.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:shopping
LANG: C++
*/
/*
DP问题，多重背包模型
这么长时间了，第一次写了个五维数组，难得啊，o(∩_∩)o...哈哈
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#define MAXV 6
#define MAXE 1000
#define cin fin
using namespace std;

ifstream fin("shopping.in");
ofstream fout("shopping.out");

int dp[6][6][6][6][6];
int code[1000];  //index of code
int price[6];    //price of unique product
int need[6];     //need of each product
int spnum[1000];
int sprice[1000];
int sp[1000][6][2];
int n,s,minv;
int main()
{
	int i,j,k,a,b,c,d,e;
	memset(code,0,sizeof(code));
	memset(sp,0,sizeof(sp));
	cin>>s;
	for(i=1,j=1;i<=s;i++){
		cin>>spnum[i];
		for(k=1;k<=spnum[i];k++){
			cin>>a;
			if(code[a]!=0) {sp[i][code[a]][0]=a;  cin>>sp[i][code[a]][1];}
			else {code[a]=j++;sp[i][code[a]][0]=a; cin>>sp[i][code[a]][1];}
		}
		cin>>sprice[i];
	}
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a;
		if(code[a]==0) code[a]=j++;
		cin>>need[code[a]]>>price[code[a]];
	}
	int temp[6];
	dp[0][0][0][0][0]=0;
	for(a=0;a<=need[1];a++)
		for(b=0;b<=need[2];b++)
			for(c=0;c<=need[3];c++)
				for(d=0;d<=need[4];d++)
					for(e=0;e<=need[5];e++)
						if(a+b+c+d+e!=0){
							minv=a*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5];
							int pt=minv;
							for(i=1;i<=s;i++){
								memset(temp,0,sizeof(temp));
								for(j=1;j<=5;j++) temp[code[sp[i][j][0]]]=sp[i][j][1];
								if(a>=temp[1] && b>=temp[2] && c>=temp[3] && d>=temp[4] &&e>=temp[5]){
									pt=sprice[i]+dp[a-temp[1]][b-temp[2]][c-temp[3]][d-temp[4]][e-temp[5]];
									if(pt<minv) minv=pt;
								}
							
							}
						dp[a][b][c][d][e]=minv;
	}
	fout<<dp[need[1]][need[2]][need[3]][need[4]][need[5]]<<endl;
	return 0;
}