题目链接 01背包裸题 直接上模板
//背包裸题 #include <algorithm> #include<iostream> #include<cstdio> using namespace std; const int MAXM = 100+5; int dp[MAXM + 1][MAXM + 1]; int main() { int T,M,v[MAXM],w[MAXM]; cin >> T >> M; for (int i = 0; i < M; i++) { scanf("%d %d", &w[i], &v[i]); //消耗时间即可看做为重量 } //DP for (int i = M - 1; i >= 0; i--) { for (int j = 0; j <= T; j++) { if (j < w[i]) { dp[i][j] = dp[i + 1][j]; } else { dp[i][j] = max( dp[i + 1][j],dp[i + 1][j - w[i]] + v[i] ); } } } cout << dp[0][T] << endl; }