文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 单源最短路径的问题
侵权投诉

单源最短路径的问题

单源最短路径的问题的c程序代码

void knapsack(Type *v,int *w,int c,int n,Type m[][100])

{//构造矩阵m[][],得出-1背包问题的最优值;

int jMax=min(w[n]-1,c);//c++库函数中求返回两数的较小值; for(int j=0;j<=jMax;j++) m[n][j]=0;

for(int j=w[n];j<=c;j++) m[n][j]=w[n];

for(int i=n-1;i>=1;i--){

jMax=min(w[i]-1,c);

for(int j=0;j<jMax;j++) m[i][j]=m[i+1][j];

for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+w[i]); //c++库函数中求返回两数的较大值;}}

template <class Type>

void traceback(Type m[][100],int *w,int c,int n,int x[])

{//构造x数组,得出最优解决方案;

int i;

for(i=1;i<n;i++){

if(m[i][c]==m[i+1][c]) x[i]=0;

else{

x[i]=1;

c-=w[i];}}

x[n]=(m[n][c])?1:0;}

int main(){

int w[100],v[100],x[100],m[100][100],c,n,wz=0;

//wz计数背包中总的物品重量; cout<<"请输入集装箱数:"; cin>>n; cout<<endl<<"请输入第一艘轮船的载重量:"; cin>>c; cout<<endl<<n<<"个集装箱的编号为:"; cout<<endl; for(int i=1;i<=n;i++) cout<<i<<" ";

cout<<endl<<n<<"个集装箱的重量为:";

for(int i=1;i<=n;i++) cin>>w[i];

knapsack(v,w,c,n,m);

traceback(m,w,c,n,x);

cout<<endl<<"集装箱:"; if(x[i]==1) cout<<i<<" ";} for(int i=1;i<=n;i++){

cout<<"在轮船上。"<<endl;

cout<<endl<<"轮船上的集装箱重量分别为:";

for(int i=1;i<=n;i++){

if(x[i]==1) { cout<<w[i]<<" "; wz+=w[i];}} cout<<endl;

上一页第3页

你可能喜欢

  • 初二数学提高训练
  • 分支限界法
  • 勾股定理复习
  • 最短路线问题
  • 算法实验报告
  • 最短路径算法
  • 操作系统实验
  • 存储管理

热门文档

相关文档

  • 单源最短路径问题-Dijkstra

    单源最短路径问题 所谓单源最短路径问题是指:已知图 G=(V,E) ,我们希望找出从某给定的源结点 S∈V 到 V 中的每个结点的最短路径。 首先,我们可以发现有...

  • 单源最短路径问题

    s a b 3 f c 4 h 2 e d u g 4 9 5 12 6 单源路径问题的解空间树 节点旁数字为当前路长 s 当前最短路程为4,将其 扩展即走aeq,aek;计算 最...

  • 单源最短路径问题-Dijkstra

    单源最短路径问题 所谓单源最短路径问题是指:已知图 G=(V,E) ,我们希望找出从某给定的源结点 S∈V 到 V 中的每个结点的最短路径。 首先,我们可以发现...

  • 单源最短路径问题实验参考报告

    实验题目: 实验题目:单源最短路径问题告诉您寝的人 下周二( 周)做实验 记得写~~~ 告诉您寝的人 下周二(13 周)做实验 记得写~~~ 2010 年 11 月 18 日...

  • 单源最短路径问题

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 单源最短路径问题 单源最短路径问题单源最短路径问题隐藏>> 单源最...

  • 单源最短路径问题 徐林林4

    1 单源最短路径问题徐林林 文中首先介绍单源最 摘要: 本文对实际应用中的单源最短路径问题给出了一种贪心解法。 短路径问题, 然后对其进行分析和讨论, 并证明...

  • 单源最短路径(两种方法)

    单源最短路径(两种方法)_IT/计算机_专业资料。单源最短路径(贪心算法、分支限界法)单源最短路径计科一班 李振华 2012040711 1、 问题描述 给定带权有向图 ...

  • 单源最短路径

    单源最短路径的变体在本章中,我们将重点讨论单源最短路径问题:已知图 G = (V , E ) ,我们希望找 出从某给定源顶点 s ∈ V 到每个顶点 v ∈ V 的最...

  • 单源最短路径

    单源最短路径问题 I 用贪心算法求解贪心算法是一种经典的算法, 通常以自顶向下的方式进行, 以迭代的方式作出相继的贪 心选择, 每作一次贪心选择就将所求问题...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email