本文参考 https://www.cnblogs.com/Kescholar/p/18306136
这一题可能对高手来说就能轻而易举的看出是个01背包，但是对于我这种小白还是要经过详细的分析才可以理解。
我们题目要求的是获得的最大报酬，题目的影响因素有三个：工作时长、工作截止时间、对应的报酬，那么怎么样合理的去安排，选什么变量来让他成为一道01背包的题呢？
对于01背包，我们知道，每个物品有各自的重量和价值，我们要在有限的背包容量下，求装入的物品最大价值，每一个我们的dp【i】【j】代表的是前i个物品，当前背包容量为j下的最优解，那么如果我们把i当成前i个工作，把j当前工作的截止时间，那么此时的dp【i】【j】就是做了i件工作，截止时间长度j下的报酬最大值，那么此时就可以模仿01背包的做法来实现了。
对于截止时间，其实就相当于背包当前的体积，我觉得很多人应该会在这里有困惑，所以应该先对截止时间排序，从小到大排完以后，再去进行dp
这是17分的版本，使用二维数组方便理解一点，但是肯定需要滚动数组，不然会卡空间
#include <bits/stdc++.h>
using namespace std;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
int t,d,p;
};
int main()
{
//dp[i][j]代表前i个事件，截至时间为j下的最大报酬
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int dp[100][1000];
vector<node>ve(n+1);
for(int i=1;i<=n;i++) cin>>ve[i].t>>ve[i].d>>ve[i].p;
//先按照截至时间来排序，尽可能多的干更多的活
sort(ve.begin(),ve.end(),[](node x,node y){
return x.d<y.d;
});
dp[0][0]=0;//初始化
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=ve[i].d;j++)
{
//如果截至时间小于干这件事的时长 说明这件事不能干
if(j<ve[i].t) dp[i][j]=dp[i-1][j];//最大报酬等于干完上一件事情的报酬
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-ve[i].t]+ve[i].p);
//同理背包
res=max(res,dp[i][j]);
}
}
cout<<res<<endl;
}
}
滚动数组就满分了
#include <bits/stdc++.h>
using namespace std;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
int t,d,p;
};
int main()
{
//dp[i][j]代表前i个事件，花了j个时间长度
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int dp[5005]={0};
vector<node>ve(n+1);
for(int i=1;i<=n;i++) cin>>ve[i].t>>ve[i].d>>ve[i].p;
sort(ve.begin(),ve.end(),[](node x,node y){
return x.d<y.d;
});
int res=0;
for(int i=1;i<=n;i++)
{
//滚动数组确保了截止时间大于做完这件事的市场
for(int j=ve[i].d;j>=ve[i].t;j--)
{
dp[j]=max(dp[j],dp[j-ve[i].t]+ve[i].p);
res=max(res,dp[j]);
}
}
cout<<res<<endl;
}
}