| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 576 人关注过本帖
标题:这个程序的算法?????????????????
只看楼主 加入收藏
sailer
Rank: 1
等 级:新手上路
帖 子:69
专家分:0
注 册:2005-10-12
收藏
 问题点数:0 回复次数:4 
这个程序的算法?????????????????

下面是动态规划的背包算法(0--1背包)请大家分析以下。
#define ymax 100

#define nmax 100

float f[nmax][ymax];

void Knapsack(float p[],int w[],int c,int n)

{ int y=0,i=0;

for(y=0;y<ymax;y++) f[n][y]=0;

for(y=w[n];y<=c;y++) f[n][y]=p[n];

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

for(y=0;y<ymax;y++) f[i][y]=f[i+1][y];

for(y=w[i];y<=c;y++)

f[i][y]=(f[i+1][y]>(f[i+1][y-w[i]]+p[i]))?f[i+1][y]:(f[i+1][y-w[i]]+p[i]); }

f[1][c]=f[2][c];

if(c>=w[1])

f[1][c]=(f[1][c]>(f[2][c-w[1]]+p[1]))?f[1][c]:(f[2][c-w[1]]+p[1]);}

void traceback(int w[],int c,int n,int x[])/*得到解向量x*/

{ int i=0;

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

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

else{ x[i]=1; c-=w[i]; }

x[n]=f[n][c]?1:0;}
请大家帮我分析以下,我有点不明白。最好加一些标注解释。谢谢!!

[此贴子已经被作者于2005-12-11 13:23:23编辑过]

搜索更多相关主题的帖子: 算法 
2005-12-11 13:23
layabout
Rank: 1
等 级:新手上路
帖 子:180
专家分:0
注 册:2005-12-2
收藏
得分:0 
动态规划的背包算法,目的是什么啊,不然怎么看??

学习不难!难的是一辈子兢兢业业,老老实实,勤勤恳恳的学习!!!
2005-12-11 13:28
sailer
Rank: 1
等 级:新手上路
帖 子:69
专家分:0
注 册:2005-10-12
收藏
得分:0 

假设给定n个物体和一个背包,物体i的重量为wi,价值为pi(I=1,2,……,n),背包能容纳的物体重量为m,要从这n个物体中选出若干件放入背包,使得放入物体的总重量小于等于m,而总价值达到最大。如果用xi=1表示将第I件物体放入背包,用xi=0表示未放入,则问题变为选择一组xi(I=0,1)

这里的xi只能取0或1两种值,所以称为0-1背包问题


希望大家多多配合他人,多多帮助他人。 支持国家的 产品,尽量不买外国货。
2005-12-11 14:00
layabout
Rank: 1
等 级:新手上路
帖 子:180
专家分:0
注 册:2005-12-2
收藏
得分:0 
我想了个算法,先求pi/wi(单位价值),

然后排序,大的先放,

用m去减直到m<0


学习不难!难的是一辈子兢兢业业,老老实实,勤勤恳恳的学习!!!
2005-12-11 15:28
layabout
Rank: 1
等 级:新手上路
帖 子:180
专家分:0
注 册:2005-12-2
收藏
得分:0 

有漏洞,好象有点排列,组合的意思....


看不懂就去看数据结构p多少页忘了,

二叉树那里...

[此贴子已经被作者于2005-12-13 20:03:56编辑过]


学习不难!难的是一辈子兢兢业业,老老实实,勤勤恳恳的学习!!!
2005-12-11 15:43
快速回复:这个程序的算法?????????????????
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026559 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved