| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 910 人关注过本帖
标题:[求助]这个程序的错误是什么
只看楼主 加入收藏
wolaixiazai
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2007-4-11
收藏
 问题点数:0 回复次数:3 
[求助]这个程序的错误是什么
这是用回溯法做0-1背包问题的程序,程序运行时出错,我估计是使用递归函数时出错,但是我无法找出错误原因。请大家帮帮忙,告诉我错在哪里了。
#include <stdio.h>
int     cv;//当前价值
int     cw;//当前重量
int     bestv;//当前最优价值
int     *bestx;//当前最优解
int     c=10;//背包容量
int     n=5;//物品个数
//计算当前结点处的上界
float   Bound(int   i,int   *v,int   *w)
{   int   left=c-cw;             //剩余容量
    float   b=(float)cv;
    while(i <=n&&w[i] <=left)
{ left-=w[i];
                b+=v[i];
i++;
}
    //装满背包
    if(i <=n)b+=(float)(v[i]/w[i])*left;
    return   b;
}
void   Backtrack(int   i,int   *v,int   *w,int   *x)
{   if(i> n)
{for(int   j=1;j <=n;j++)
    bestx[j]=x[j];
    bestv=cv;
}   
    else
{for(int   t=0;t <=1;t++)
{
          x[i]=t;
                  if(cw+w[i] <=c&&Bound(i+1,v,w)> bestv)
{if(x[i]==1)
{cw+=w[i];cv+=v[i];}
          Backtrack(i+1,v,w,x);
  if(x[i]==1)
{cw-=w[t];cv-=v[t];}
}
}
}
   
    if(Bound(i+1,v,w)> (float)bestv)//搜索右子树
{x[i]=0;
  Backtrack(i+1,v,w,x);
}
}

void   main()
{int   w[6]={0,2,2,6,5,4},v[6]={0,6,3,5,4,6};//0号单元不用
  int   x[6];//当前解
  cv=0;
  cw=0;
  bestv=0;   
  Backtrack(1,v,w,x);
  printf("选择的物品:");
  for(int   i=1;i <=5;i++)
      if(bestx[i]==1)printf("%   d",i);
  printf("\n");
  printf("最大价值和为:%d\n",bestv);
}
搜索更多相关主题的帖子: int float left 容量 
2007-12-14 21:46
wolaixiazai
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2007-4-11
收藏
得分:0 
Who can help me?
2007-12-15 17:23
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
程序没缩进别人懒得看。
2007-12-15 20:39
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
程序代码:
 #include <stdio.h>
int cv;//当前价值
int cw;//当前重量
int bestv;//当前最优价值
int bestx[6];//当前最优解
int c=10;//背包容量
int n=5;//物品个数
//计算当前结点处的上界
float Bound(int i,int *v,int *w) {
    int left=c-cw;     //剩余容量
    float b=(float)cv;
    while (i <=n&&w[i] <=left) {
        left-=w[i];
        b+=v[i];
        i++;
    }
//装满背包
    if (i <=n)b+=(float)(v[i]/w[i])*left;
    return b;
}
void Backtrack(int i,int *v,int *w,int *x) {
    if (i> n) {
        for (int j=1;j <=n;j++)
            bestx[j]=x[j];
        bestv=cv;
    } else {
        for (int t=0;t <=1;t++) {
            x[i]=t;
            if (cw+w[i] <=c&&Bound(i+1,v,w)> bestv) {
                if (x[i]==1) {
                    cw+=w[i];
                    cv+=v[i];
                }
                Backtrack(i+1,v,w,x);
                if (x[i]==1) {
                    cw-=w[t];
                    cv-=v[t];
                }
            }
        }
    }

    if (Bound(i+1,v,w)> (float)bestv) { //搜索右子树
        x[i]=0;
        Backtrack(i+1,v,w,x);
    }
}

void main() {
    int w[6]={0,2,2,6,5,4},v[6]={0,6,3,5,4,6};//0号单元不用
    int x[6];//当前解
    cv=0;
    cw=0;
    bestv=0;
    Backtrack(1,v,w,x);
    printf("选择的物品:");
    for (int i=1;i <=5;i++)
        if (bestx[i]==1)printf("% d",i);
    printf("\n");
    printf("最大价值和为:%d\n",bestv);
    getchar();
} 
格式化了下你的代码,并且不会报错了。不过没仔细看。你运行下看,有没有别的问题……

专心编程………
飞燕算法初级群:3996098
我的Blog
2007-12-16 05:54
快速回复:[求助]这个程序的错误是什么
数据加载中...
 
   



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

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