dp背包

#include<bits/stdc++.h> using namespace std; int p[10005]; int w[1005]; int dp[10005][3005]; int main(){ int m,n; cin>>m>>n; for(int i = 1;i<=n;i++){ cin>>w[i]; cin>>p[i]; } for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(w[i]<=j) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]); else dp[i][j] = dp[i-1][j]; } } cout<<dp[n][m]; return 0; }

模板题，没什么好说的

dp模板啊

点赞

#include <bits/stdc++.h> using namespace std; int dp[101][1010],b[110],f[110]; int a,m; int main(){ }

#include<bits/stdc++.h> using namespace std; int t,m; int c[105]; int v[105]; int dp[105][1005]; int main(){ cin>>t>>m; for(int i=1;i<=m;i++) { cin>>c[i]>>v[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=t;j++) { dp[i][j] = dp[i-1][j]; if(j>=c[i]) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]]+v[i]); } } cout<<dp[m][t]; return 0; }

(这篇题解可能和别的题解不同,一共有两个完整的AC代码) 解题思路 很典型的01背包问题 可以选择二维dp或者一维dp 二维DP思路: 1. 遍历每一个状态 2. 根据前一个状态，选择装或者不装之间的较大值 3. 取最末状态，最大容量为答案 AC代码 二维DP代码 > 执行用时 8ms > 内存消耗 0.97MB 一维DP代码 > 执行用时 5ms > 内存消耗 0.59MB 欢迎加入团队 制作题解不易,跪求点赞!!!

本蒟蒻第n次写题解 一维dp： 二维的： 其实题目很简单，像我一样的蒟蒻都能做

old big 来拯救你们了 #include<bits/stdc++.h> using namespace std; int t,m; int c[105],v[105]; int dp[105][1005]; int main(){ cin>>t>>m; for(int i=1;i<=m;i++){ cin>>c[i]>>v[i]; } for(int i=1;i<=m;i++){ for(int j=1;j<=t;j++){ dp[i][j] = dp[i-1][j]; if(j>=c[i]) dp[i][j] = max( dp[i-1][j] , dp[i-1][j-c[i]]+v[i]); } } cout<<dp[m][t]; return 0; }

二维dp： 一维：

深度优先搜索

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1005; int w[N]; int p[N]; int n,m; int dp[N][N]; int main(){ int m,n; cin>>m>>n; for(int i = 1;i<=n;i++){ cin>>w[i]; cin>>p[i]; } for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(w[i]<=j) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]); else dp[i][j] = dp[i-1][j]; } } cout<<dp[n][m]; return 0; }

经典01背包

AC代码： #include<bits/stdc++.h> using namespace std; int m,t; int c[101]; int v[101]; int dp[101][1001]; int main(){ cin >> t >> m; for(int i = 1;i <= m;i ++){ cin >> c[i] >> v[i]; } for(int i = 1;i <= m;i ++){ for(int j = 1;j <= t;j ++){ dp[i][j] = dp[i-1][j]; if(j >= c[i]) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]] + v[i]); } } cout << dp[m][t]; return 0; }