?? usaco_3_3_2_shopping_多重背包.cpp
字號:
/*
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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -