题目链接：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[2][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=0; 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=1;i<=n;i++) scanf("%d%d",&w[i],&s[i]); memset(dp[0],0,sizeof(dp[0])); int max_1=0; int max_2=0; prev=0,now=1; for(int i=1;i<=n;i++) { memset(dp[now],-1,sizeof(dp[now])); int num1=min(w[i]/w1,s[i]/s1); int tmp; for(int p=0;p<=num1;p++) { int num2=min((w[i]-p*w1)/w2,(s[i]-p*s1)/s2); if(p==0) tmp=num2; for(int q=0;q<=num2;q++) { int nn=put(i,p,q); for(int k1=0;k1<=max_1;k1++) for(int k2=0;k2<=max_2;k2++) { if(dp[prev][k1][k2]!=-1) 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=0; for(int i=0;i<=max_1;i++) for(int j=0;j<=max_2;j++) { if(dp[prev][i][j]!=-1) { 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 0; }