8 条题解
-
4
#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一维数组优解,制作不易,点个赞再走吧
-
1
时间空间复杂度最小一维数组加注释谁要
#include <iostream> #include <algorithm> using namespace std; int main() { int m, n; // 背包容量和物品数量 cin >> m >> n; int W[n]; // 物品重量 int C[n]; // 物品价值 // 输入物品的重量和价值 for (int i = 0; i < n; i++) { cin >> W[i] >> C[i]; } // dp[j] 表示背包容量为 j 时的最大价值 int dp[m + 1] = {0}; // 初始化为0,表示容量为0时价值为0 // 动态规划填表 for (int i = 0; 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] << endl; return 0; }
-
0
#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; }
-
-1
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]; }
-
-3
-
-3
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];//输出最优结果 }
-
-4
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
- 标签
- 递交数
- 272
- 已通过
- 102
- 上传者