Lapsec 2014-12-30 12:01
浏览 980

01背包回溯法计算起来非常慢,有木有算法大大帮忙看看

#include
#include
#include
#include
#include
#include

using namespace std;
int n;//物品数量
double c;//背包容量
double v[9000];//各个物品的价值
double w[9000];//各个物品的重量
double cw = 0.0;//当前背包重量
double cp = 0.0;//当前背包中物品价值
double bestp = 0.0;//当前最优价值
double perp[9000];//单位物品价值排序后
int order[9000];//物品编号
int put[9000];//fprintf(fp2,"%d %d\n",i,put[i]);设置是否装入

//按单位价值排序
/*void knapsack()
{
int i,j;
int temporder = 0;
double temp = 0.0;

for(i=1;i<=n;i++)
    perp[i]=v[i]/w[i];
for(i=1;i<=n-1;i++)
{
    for(j=i+1;j<=n;j++)
        if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
    {
        temp = perp[i];
        perp[i]=perp[i];
        perp[j]=temp;

        temporder=order[i];
        order[i]=order[j];
        order[j]=temporder;
}

}
}*/
//回溯函数
void backtrack(int i)
{
double bound(int i);
if(i>n)
{
bestp = cp;
return;
}
if(cw+w[i]<=c)
{
cw+=w[i];
cp+=v[i];
put[i]=1;
backtrack(i+1);
cw-=w[i];
cp-=v[i];
}
if(bound(i+1)>bestp)//符合条件搜索右子数
backtrack(i+1);
}

//计算上界函数
double bound(int i)
{
double leftw= c-cw;//剩余背包容量
double b = cp;//当前背包里面的价值
while(i<=n&&w[i]<=leftw)//!!!重点在这里把w[i]<=leftw输出的结果是正确的但是跑起来非常慢要十几秒。如果没去掉的话输出错误。按思路的话不应该去掉的,有木有算法大大
{
leftw-=w[i];
b+=v[i];
i++;
}
if(i<=n)
b+=v[i]/w[i]*leftw;
return b;
}

int main()
{
clock_t start,finish;
FILE *fp1;
FILE *fp2;
int i;
fp1=fopen("..\.\test.txt","r"); //以只读方式打开文件
if(!fp1)printf("File Open Error!!");
fscanf(fp1,"%lf%d",&c,&n);

for(int i=1;i<=n;i++)
{
    fscanf(fp1,"%lf%lf",&w[i],&v[i]);
    order[i]=i;
    perp[i]=v[i]/w[i];
    put[i]=0;
}
 //printf("%lf%lf",w[50],v[50]);
start = clock();
//knapsack();
backtrack(1);

fp2=fopen("..\\.\\result.txt","w");  //以只写方式打开文件
fprintf(fp2,"%lf\n",bestp);
for(i=1;i<=n;i++)
{
    fprintf(fp2,"%d %d\n",i,put[i]);
}

printf("最有价值为:%lf\n",bestp);
printf("需要装入的物品编号是:");
for(i=1;i<=n;i++)
{
    if(put[i]==1);
        //printf("%d ",order[i]);
}
finish = clock();
printf("%lf\n",finish-start);
cout<<(finish-start)<<endl;
return 0;

}


测试数据:
300 50
71 26
34 59
82 30
23 19
1 66
88 85
12 94
57 8
10 3
68 44
5 5
33 1
37 41
69 82
98 76
24 1
26 12
83 81
16 73
26 32
18 74
43 54
52 62
71 41
22 19
65 10
68 65
8 53
40 56
40 53
24 70
72 66
16 58
34 22
10 72
19 33
28 96
13 88
34 68
98 45
29 44
31 61
79 78
33 78
60 6
74 66
44 11
56 59
54 83
17 48

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 MATLAB动图问题
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题