Floyd 弗洛伊德算法+背包问题
2023-08-20 14:52:49
发布于：河北
3阅读
0回复
0点赞
Floyd-Warshall（弗洛伊德算法）：
核心参考代码：
memset(mp,0x3f,sizeof(d));
for(int i=1; i<=n; i++)
{
d[i][i]=0;
for(int j=1; j<=n; j++)
{
cin>>d[i][j];
}
}
for(int k = 1; k<=n; k++)
{
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=n; j++)
{
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
}
}
关系：
距离>1的是间接朋友，距离<1的没有关系，默认值为无穷大
背包问题：
01背包（最基础的背包问题）：
有N件物品和一个容量为v的背包。第i件物品的体积是c[1]，
价值是w[i]。求解将那些物品装入背包可使价值总和最大
01背包特点：
每种物品只有一件，可以选择放或不放。
用子问题定义状态：即dp[i][v]表示前i件物品放入一个容量为v的背包可以获得的最大价值
01背包优化：
dp[i]=max(dp[i],dp[i-v]+w)
tip:v==空间,w==价值
完全背包公式:
类似于01背包但01背包为for(intj=m;j>=v;i--)
而完全背包为for(int j=v;j<=m;j++);
多重背包:
for(k=1; k<=n; k++)
{
cin>>v>>w>>x;
for(int i=1; i<=x; i++)
{
for(j=v*i; j<=m; j++)
{
f[j]=max(f[j],f[j-v*i]+i*w);
}
}
}
或将多重背包中大于一个的拆分开来，化简为01背包问题，但对应的时间复杂度会增加。
有帮助，赞一个