昨天学了下背包，cpu都要烧干了，写了1上午了

#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; }

经典01背包

#include "stdio.h" #include "iostream" using namespace std; int w[105], val[105]; int dp[1005]; int main() { int t,m,res=-1; scanf("%d%d",&t,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&w[i],&val[i]); } for(int i=1;i<=m;i++) { for(int j=t;j>=0;j--) { if(j>=w[i]) { dp[j]=max(dp[j-w[i]]+val[i], dp[j]); } } } printf("%d",dp[t]); return 0; }

01背包

#include<bits/stdc++.h> using namespace std; int p[1005];//price int w[1005];//time int dp[1005][1005]; int main(){ int n , m; cin >> n >> m; for(int i = 1;i <= m;i++){ cin >> w[i];//time cin >> p[i];//price } for(int i = 1;i <= m;i++){//枚举pill数 for(int j = 1;j <= n;j++){//枚举time //dp方程转移式 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[m][n]; return 0; }