第一行输入1.时间t2.背包数量n
第二—n+1行输如第i+1行第i个背包的1.时间2.是金钱
输出最大价值
#include <iostream>
using namespace std;
int _max=0;
int t,n;
int jt[1010][110]={2000};
int sp[110][2]; //sp[i][0] 为第i个的时间 sp[i][1]是第一个的价值
void dp(int money_got,int time_left,int step){
if(step==n||jt[time_left][step]!=2000){
if(jt[time_left][step]!=2000)money_got+=jt[time_left][step];
if(money_got>_max)_max=money_got;
return;
}
if(time_left>=sp[step][0])
dp(money_got+sp[step][1],time_left-sp[step][0],step+1);//要
dp(money_got,time_left,step+1);//不要
jt[time_left][step]=money_got; //好像是这里出问题了
}
int main(){
cin >> t >> n;
for(int i=1;i<=n;i++){
cin >> sp[n][0] >> sp[n][1];
}
dp(0,t,1);
cout << _max << endl;
return 0;
}
第二—n+1行输如第i+1行第i个背包的1.时间2.是金钱
输出最大价值
#include <iostream>
using namespace std;
int _max=0;
int t,n;
int jt[1010][110]={2000};
int sp[110][2]; //sp[i][0] 为第i个的时间 sp[i][1]是第一个的价值
void dp(int money_got,int time_left,int step){
if(step==n||jt[time_left][step]!=2000){
if(jt[time_left][step]!=2000)money_got+=jt[time_left][step];
if(money_got>_max)_max=money_got;
return;
}
if(time_left>=sp[step][0])
dp(money_got+sp[step][1],time_left-sp[step][0],step+1);//要
dp(money_got,time_left,step+1);//不要
jt[time_left][step]=money_got; //好像是这里出问题了
}
int main(){
cin >> t >> n;
for(int i=1;i<=n;i++){
cin >> sp[n][0] >> sp[n][1];
}
dp(0,t,1);
cout << _max << endl;
return 0;
}