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

下面是动态规划的背包算法(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;}
请大家帮我分析以下,我有点不明白。最好加一些标注解释。谢谢!!

搜索更多相关主题的帖子: 动态规划 算法 背包 int float 
2005-12-09 14:59
快速回复:0---1背包问题的动态规划算法
数据加载中...
 
   



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

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