竞赛
考级
dp背包
wangsuyang
#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; }
法兰西玫瑰
模板题,没什么好说的
TX_Bernie
#include <bits/stdc++.h> using namespace std; int dp[101][1010],b[110],f[110]; int a,m; int main(){ }
一枚button
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; }
耐摔王old big
#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 欢迎加入团队 制作题解不易,跪求点赞!!!
唱跳坤
HHT2011
#include <bits/stdc++.h> using namespace std; int T,m; int t[110],c[110],dp[1010]; int main(){ cin>>T>>m; for(int i=1;i<=m;i++){ cin>>t[i]>>c[i]; } for(int i=1;i<=m;i++){ for(int j=T;j>=t[i];j--){ dp[j]=max(dp[j],dp[j-t[i]]+c[i]); } } cout<<dp[T]; return 0; }
Aurua
Erling·Haalanddd
昨天学了下背包,cpu都要烧干了,写了1上午了
/*注释*/
经典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; }
兰美赛赛
深度优先搜索
AC君
亚洲卷王
初饮喂来
#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; }
许肄霄
模板 : #include<bits/stdc++.h> using namespace std; int dp[2001]; int w[205],v[205]; int n,m; int main(){ cin>>n>>m; }
PE君
共23条