模板
2023-08-20 14:48:07
发布于：广东
0阅读
0回复
0点赞
01背包模板
#include<iostream>
using namespace std;
const int maxm = 2001, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxm];
int main(){
cin>>m>>n;//背包容量m和物品数量n
for (int i=1; i <= n; i++)
cin>>w[i]>>c[i];//每个物品的重量和价值
//设f(v)表示重量不超过v公斤的最大价值
for (int i=1; i <= n; i++)
for (int v = m; v >= w[i]; v--)
if (f[v-w[i]]+c[i]>f[v])
f[v] = f[v-w[i]]+c[i];
cout<<f[m];// f(m)为最优解
return 0;
}
01背包一维模板
#include<iostream>
using namespace std;
const int maxm = 2001, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxm];
int main(){
cin>>m>>n;//背包容量m和物品数量n
for (int i=1; i <= n; i++)
cin>>w[i]>>c[i];//每个物品的重量和价值
//设f(v)表示重量不超过v公斤的最大价值
for (int i=1; i <= n; i++)
for (int v = m; v >= w[i]; v--)
if (f[v-w[i]]+c[i]>f[v])
f[v] = f[v-w[i]]+c[i];
cout<<f[m];// f(m)为最优解
return 0;
}
完全背包二维模版
#include<iostream>
using namespace std;
const int maxm = 201, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxn][maxm];
int main(){
cin>>m>>n;//背包容量m和物品数量n
for (int i = 1; i <= n; i++)
cin>>w[i]>>c[i];//每个物品的重量和价值
//f[i][v]表示前i件物品，总重量不超过v的最优价值
for (int i = 1; i <= n; i++)
for (int v = 1; v <= m; v++)
if (v < w[i])
f[i][v] = f[i-1][v];
else{
if (f[i-1][v] > f[i][v-w[i]]+c[i]){
f[i][v] = f[i-1][v];
}else{
f[i][v] = f[i][v-w[i]]+c[i];
}
}
cout<<"max="<<f[n][m];// f[n][m]为最优解
return 0;
}
完全背包一维模版
#include<bits/stdc++.h>
using namespace std;
int g[105][105];//存图
int x,y;//n跟顶点，m条变
int n,m;//x-y构成边
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){//m条边
cin>>x>>y;
//无向图
g[x][y]=g[y][x]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout <<g[i][j]<<" ";
}
cout <<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个