题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=13
很经典的一个DP的题目
定义dp[i][num1][num2]表示前i个车装num1个装备1和num2个装备2之后最多能装的装备3的个数
那么dp[i][p+x][q+y]=max(dp[i][p+x][q+y],dp[i-1][p][q]+num(x,y));
其中num(x,y)表示第i辆车装x个装备1和y个装备2后还能最多装的装备3的个数
x,y的范围即为第辆车的可以装的装备1和装备2的最大个数
可以看出dp[i]只与dp[i-1]有关，要用滚动数组，否则会超内存
代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define maxn 550
#define maxn_1 110
using namespace std;
int dp[][maxn][maxn];
int w[maxn_1];
int s[maxn_1];
int w1,s1,d1;
int w2,s2,d2;
int w3,s3,d3;
int c1,c2,c3,d4;
int prev,now;
int put(int num,int p,int q)
{
int nw=(w[num]-p*w1-q*w2)/w3;
int ns=(s[num]-p*s1-q*s2)/s3; return min(nw,ns);
}
int main()
{
int n;
int icase=;
while(scanf("%d",&n) != EOF&& n)
{
scanf("%d%d%d",&w1,&s1,&d1);
scanf("%d%d%d",&w2,&s2,&d2);
scanf("%d%d%d",&w3,&s3,&d3);
scanf("%d%d%d",&c1,&c2,&c3);
scanf("%d",&d4); for(int i=;i<=n;i++)
scanf("%d%d",&w[i],&s[i]);
memset(dp[],,sizeof(dp[])); int max_1=;
int max_2=;
prev=,now=;
for(int i=;i<=n;i++)
{
memset(dp[now],-,sizeof(dp[now]));
int num1=min(w[i]/w1,s[i]/s1);
int tmp;
for(int p=;p<=num1;p++)
{
int num2=min((w[i]-p*w1)/w2,(s[i]-p*s1)/s2);
if(p==) tmp=num2; for(int q=;q<=num2;q++)
{
int nn=put(i,p,q);
for(int k1=;k1<=max_1;k1++)
for(int k2=;k2<=max_2;k2++)
{
if(dp[prev][k1][k2]!=-)
dp[now][k1+p][k2+q]=max(dp[now][k1+p][k2+q],dp[prev][k1][k2]+nn);
}
}
} max_1+=num1;
max_2+=tmp;
swap(now,prev); }
int ans=;
for(int i=;i<=max_1;i++)
for(int j=;j<=max_2;j++)
{
if(dp[prev][i][j]!=-)
{
int num_4=min(min(i/c1,j/c2),dp[prev][i][j]/c3);
ans=max(max(ans,i*d1+j*d2+dp[prev][i][j]*d3),(i-num_4*c1)*d1+(j-num_4*c2)*d2+(dp[prev][i][j]-num_4*c3)*d3 +num_4*d4);
}
}
if(icase++) cout<<endl;
cout<<"Case "<<icase<<": "<<ans<<endl;
}
return ;
}