DP(递归形式). 用f[a0,a1,a2,a3,a4]表示每种商品数量分别为a0,a1,a2,a3,a4时的最小价格.则f[a0,a1,a2,a3,a4]=min{f[a0-b0,a1-b1,a2-b2,a3-b3,a4-b4]+priceb,f[a0-c0,a1-c1,a2-c2,a3-c3,a4-c4]+pricec,......}.bi表示第一种优惠组合中各商品的数量,priceb为对应的优惠价. 以此类推. 此题用记忆化DP较好, 详细见代码:
#include<iostream>
#include<map>
using namespace std;
int B,S,N;
int num[6];
int offer[105][6];
int price[105];
int f[6][6][6][6][6];
int dp(int a0,int a1,int a2,int a3,int a4)
{
if(f[a0][a1][a2][a3][a4]!=-1)
return f[a0][a1][a2][a3][a4];
int i,j,temp=100000000;
for(i=0;i<B+S;i++)
{
if(a0>=offer[i][0]&&a1>=offer[i][1]&&a2>=offer[i][2]&&a3>=offer[i][3]&&a4>=offer[i][4])
{
if(temp>dp(a0-offer[i][0],a1-offer[i][1],a2-offer[i][2],a3-offer[i][3],a4-offer[i][4])+price[i])
temp=dp(a0-offer[i][0],a1-offer[i][1],a2-offer[i][2],a3-offer[i][3],a4-offer[i][4])+price[i];
}
}
f[a0][a1][a2][a3][a4]=temp;
return temp;
}
int main()
{
int i,j,c,k,p,s;
map<int,int> ref;
memset(num,0,sizeof(num));
memset(offer,0,sizeof(offer));
scanf("%d",&B);
for(i=0;i<B;i++)
{
scanf("%d%d%d",&c,&k,&p);
ref[c]=i;
num[i]=k;
price[i]=p;
offer[i][i]=1;
}
scanf("%d",&S);
for(i=B;i<B+S;i++)
{
scanf("%d",&N);
for(j=0;j<N;j++)
{
scanf("%d%d",&c,&k);
offer[i][ref[c]]=+k;
}
scanf("%d",&price[i]);
}
memset(f,-1,sizeof(f));
f[0][0][0][0][0]=0;
int ans=dp(num[0],num[1],num[2],num[3],num[4]);
printf("%d\n",ans);
//system("pause");
return 0;
}
posted on 2010-08-20 10:05
wuxu 阅读(185)
评论(0) 编辑 收藏 引用 所属分类:
动态规划