wp:array[1..60,1..2] of longint;
xz:array[1..60] of boolean;
fj:array[1..60] of longint;
procedure px;
var i,s:longint;
begin
s:=0;
for i:=1 to b do
if xz[i]
then s:=s+wp[i,1]*wp[i,2];
if s>m
then m:=s;
end;
procedure qj(d,s:longint);
var i:longint;
begin
for i:=1 to 2 do
begin
if (wp[d,1]>s) and (i=1)
then continue;
if (i=1) and (fj[d]>0) and (not xz[fj[d]])
then continue;
if i=1
then xz[d]:=true
else xz[d]:=false;
px;
if d<b
then begin
if i=1
then qj(d+1,s-wp[d,1])
else qj(d+1,s);
end;
end;
end;
begin
readln(a,b);
for i:=1 to b do
readln(wp[i,1],wp[i,2],fj[i]);
qj(1,a);
writeln(m);
end.
#include <cmath>
#include <memory.h>
using namespace std;
int dp[30001]={0};
int main()
{
int money,n;
cin>>money>>n;
int i=1,j;
int zhu[60][2],link1[60][2]={0},link2[60][2]={0};
for(j=0;j<n;++j)
{
int v,p,q;
cin >> v >> p >> q;
if(q == 0){zhu[i][0] = v;zhu[i][1] = v*p;++i;}
else if(link1[q][0] == 0){link1[q][0] = v;link1[q][1] = v*p;}
else{link2[q][0] = v;link2[q][1] = v*p;}
}
memset(link1,0,sizeof(link1));
memset(link2,0,sizeof(link2));
int maxx = 0;
int k;
for(j=1;j<i;++j){
for(k=money;k>=zhu[j][0];k--)
{
dp[k]=max( dp[k] , dp[k-zhu[j][0]]+zhu[j][1] );
if(k-zhu[j][0]-link1[j][0]>=0)
dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]]+zhu[j][1]+link1[j][1]);
if(k-zhu[j][0]-link2[j][0]>=0)
dp[k]=max(dp[k],dp[k-zhu[j][0]-link2[j][0]]+zhu[j][1]+link2[j][1]);
if(k-zhu[j][0]-link1[j][0]-link2[j][0]>=0)
dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]-link2[j][0]]+zhu[j][1]+link1[j][1]+link2[j][1]);
maxx=max(maxx,dp[k]);
}
}
cout << maxx;
return 0;
}
#include <cmath>
using namespace std;
int dp[30001]={0};
int main()
{
int money,n;
cin>>money>>n;
int i=1,j;
int zhu[60][2]={0},link1[60][2]={0},link2[60][2]={0};
for(j=0;j<n;++j)
{
int v,p,q;
cin >> v >> p >> q;
if(q == 0){zhu[i][0] = v;zhu[i][1] = v*p;}
else if(link1[q][0] == 0){link1[q][0] = v;link1[q][1] = v*p;}
else{link2[q][0] = v;link2[q][1] = v*p;}
++i;
}
int maxx = 0;
int k;
for(j=1;j<i;++j){
for(k=money;k>=zhu[j][0];k--)
{
dp[k]=max( dp[k] , dp[k-zhu[j][0]]+zhu[j][1] );
if(k-zhu[j][0]-link1[j][0]>=0)
dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]]+zhu[j][1]+link1[j][1]);
if(k-zhu[j][0]-link2[j][0]>=0)
dp[k]=max(dp[k],dp[k-zhu[j][0]-link2[j][0]]+zhu[j][1]+link2[j][1]);
if(k-zhu[j][0]-link1[j][0]-link2[j][0]>=0)
dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]-link2[j][0]]+zhu[j][1]+link1[j][1]+link2[j][1]);
maxx=max(maxx,dp[k]);
}
}
cout << maxx;
return 0;
}
关于递归超时的解决办法还有:
转成递推
转成迭代
转成搜索+剪枝
打表
......
希望lz能满意