解题思路: 0/1背包问题
参考代码:
#include <iostream> #include<cmath> using namespace std; int T,M,ValueSum; int dp[1002][1002]; int value[102],tim[102]; int get_MaxValue(int m,int t); int main() { cin>>T>>M; for(int i=0;i<=M;++i) { for(int j=0;j<=T;++j) dp[i][j]=-1; } for(int i=1;i<=M;++i) cin>>tim[i]>>value[i]; ValueSum=get_MaxValue(1,T); cout<<ValueSum<<endl; return 0; } int get_MaxValue(int m,int t) { if(dp[m][t]>0) return dp[m][t]; if(m==M) dp[m][t]=t>=tim[m]?value[m]:0; else{ if(t>=tim[m]) dp[m][t]=max(get_MaxValue(m+1,t),get_MaxValue(m+1,t-tim[m])+value[m]); else dp[m][t]=get_MaxValue(m+1,t); } return dp[m][t]; }
0.0分
0 人评分