8 条题解
-
2余东霖 (yudonglin) LV 7 @ 2023-8-6 10:45:52
#include <cmath> #include <cstring> #include <string.h> #include <queue> #include <stack> #include <map> using namespace std; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; int n,m; int w[N],v[N],dp[205]; int main(){ cin >> m >> n; for(int i=1; i<=n; i++) cin >> w[i] >> v[i]; for(int i= 1; i<=n; i++){ for(int j=m; j>=w[i]; j--){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout << dp[m]; return 0; } //01背包0一维数组优解,制作不易,点个赞再走吧
-
12023-9-24 15:48:05@
#include <iostream> using namespace std; struct node{ int price; int time; bool flag; } a[100005]; int n, ans, l, r; int main(){ cin >> n; l = 1; for(int i = 1;i <= n;i ++) { int x, p, t; cin >> x >> p >> t; if(x == 0) { a[++r].price = p; a[r].time = t; ans += p; } else { for(int i = l;i <= r;i ++) { if(t - a[i].time > 45) { l ++; continue; } if(a[i].price >= p && a[i].flag == 0) { a[i].flag = 1; ans -= p; break; } } ans += p; } } cout << ans; return 0; }
-
02024-2-17 14:01:09@
#include<bits/stdc++.h> #pragma GCC optimize(3) #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N=310; const int INF=0x3f3f3f3f; int dp[N][N],n,m,w[N],c[N]; int main() { IOS; cin>>m>>n; for(int i=1;i<=n;++i) { cin>>w[i]>>c[i]; } for(int i=1;i<=n;++i) { for(int v=m;v>0;--v) { if(v>=w[i]) dp[i][v]=max(dp[i-1][v],(dp[i-1][v-w[i]]+c[i])); else dp[i][v]=dp[i-1][v]; } } cout<<dp[n][m]; return 0; }
-
02023-9-24 15:44:21@
P1725 0/1背包问题
本人以
坑人乐于助人为主本代码是
有很多bug没有注释的现在我要
删掉分享我的代码这是TeMeGe链接http://luogu.com
这是洛谷链接http://temege.com
现在打出我的
假真代码元神,启动
搞错了
#include using namespace std; int W[1010],V[1010]; int dp[1010][1010]; int m,n; int main() { cin>>m>>n; for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j>=W[i]){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]); } else{ dp[i][j]=dp[i-1][j]; } } } cout<<dp[n][m]; }
-
-22023-4-10 21:52:13@
-
-22023-4-9 15:49:11@
P1725 0/1背包问题
背包DP模板题,
这个屑蒟蒻并没有压缩状态注释在CODE挺详细的了
CODE
#include<bits/stdc++.h> using namespace std; int W[1010],V[1010]; int dp[1010][1010];//dp[前x件物品][已用重量]=对应最大价值 int m,n; int main() { cin>>m>>n; for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; for(int i=1;i<=n;i++){//枚举第i件物品 for(int j=1;j<=m;j++){//插入第i件物品后重量 if(j>=W[i]){//插入后重量肯定得比该物件要重吧…… dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]); //dp[i-1][j] 即为 不选该物件,不选且重量达到j的最优价值 //dp[i-1][j-W[i]]+V[i] 即为 选择该物件,那么,可以得出,在没有选择该物件时,重量为j-W[i] //故在该状态+V[i](对应物品的价格) } else{ dp[i][j]=dp[i-1][j];//见上 } } } cout<<dp[n][m];//输出最优结果 }
-
-22023-4-9 15:09:54@
#include <iostream> using namespace std; int c[10001],w[10001],dp[10001]; int main(){ int m,n; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+c[i]); cout<<dp[m]; }
-
-32023-4-10 21:49:28@
P1725 0/1背包问题
本人的第n篇题解
这题很简单,用dfs就搞定了!
代码:
#include<iostream> using namespace std; int m,n,sumw,sumc,maxnc;//sumw:用来记录重量的总和,sumc:用来记录价值的总和,maxnc:用来记录最大的总和 bool b[1000000]={0}; struct s{ int w,c;//w表示重量,c表示价值 } a[1000000]={0}; void dfs(int x){ for(int i=x;i<=n;i++){ if(sumw+a[i].w<=m&&b[i]==0){//判断sumw+这个魔法石的重量会不会超出背包重量,还要判断有没有算过 sumw+=a[i].w;//加上重量 sumc+=a[i].c;//加上价值 b[i]=1;//算过了 dfs(i); b[i]=0;//还原 sumw-=a[i].w; sumc-=a[i].c; } } maxnc=max(sumc,maxnc);//比较最大的 return; } int main(){ cin>>m>>n; for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].c;//输入数字 dfs(1); cout<<maxnc;//输出 return 0; }
制作不易,点个赞再走吧。
- 1
信息
- ID
- 1725
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 219
- 已通过
- 79
- 上传者