using namespace std; struct goodinfo { float p;//物品效益 float w;//物品重量 float X;//物品该放的数量 int flag;//物品编号 };//物品信息结构体void Insertionsort(goodinfo goods[],int n)//插入排序,按pi/wi价值收益进行排序,一般教材上按冒泡排序 { int j,i;
for(j=2;j<=n;j++) {
goods[0]=goods[j]; i=j-1; while(goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; }
goods[i+1]=goods[0]; }
}//按物品效益,重量比值做升序排列
void bag(goodinfo goods[],float M,int n) { float cu; int i,j;
for(i=1;i<=n;i++) goods[i].X=0;
cu=M;//背包剩余容量? for(i=1;icu-=goods[i].w;//确定背包新的剩余容量 } else { goods[i].X=0; }for(j=2;j<=n;j++)/*按物品编号做降序排列*/ { goods[0]=goods[j]; i=j-1;
while(goods[0].flaggoods[i+1]=goods[0]; } } cout<<\"最优解为:\"<void main() { cout<<\"|--------运用贪心法解背包问题---------|\"<goodinfo*goods;//定义一个指针 while(j) { cout<<\"请输入物品的总数量:\"; cin>>n; goods=new struct goodinfo [n+1]; cout<<\"请输入背包的最大容量:\"; cin>>M; cout<>goods[i].w; cout<<\"请输入第\"<>goods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益,重量比 cout< to run agian\"< to exit\"<>j; } }3. 单源点最短路径问题的设计与实现
#include #include using namespace std; #define MAX 999void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout<<\"请输入 起点 终点 权值(-1退出):\"; cin>>begin; if(begin==-1) break;
cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); }
void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j]void PrintPath(int *prev,int n,int begin,int end) { int *path=new int [n+1]; int i,m=n; bool k=true;path[end]=end; for(i=end-1;i>1;i--) { path[i]=prev[path[i+1]]; //构造路径 m--; } for (i=m;i<=end;i++) { cout<\"; //输出路径 } cout<<\"\\b\\b\"<<\" \"<void main() { int n,i; int v=1; cout<<\"请输入顶点个数:\"; cin>>n; int *dist=new int [n+1]; int *prev=new int [n+1]; int **c; c=new int *[n+1]; for (i=0;i<=n;i++) { c[i]=new int [n+1]; } getdata(c,n); //获取数据 int begin=1,end; cout<<\"请输入所求单源路径的 起点 终点:\"; cin>>begin>>end; v=begin; Dijkstra(n,v,dist,prev,c); //计算路径 PrintPath(prev,n,begin,end); //输出路径 system(\"pause\"); }