使用回溯法解0/1背包问题n=3,c=9_背包问题C语言算法

大家好，又见面了，我是你们的朋友全栈君。

解01背包问题有很多种方法，就我知道的就有动态规划，回溯法，分支界限法这几种，下面就列出我的回溯法解法，以供参考

int capacity; //背包容量

int n; //物品数

int weight[0..n]; //物品重量数组

int price[0..n]; //物品价值数组

int cur_weight; //当前重量

int cur_price; //当前价值

int best_price; //当前最优值

int best_solution[0..n]; //当前最优解

int cur_solution[0..n]; //当前解

//估计 装入第i个物品后能得到的最大价值, 从而做为剪枝的依据

int upper_bound(int i)

{

//计算上界

int remain_capacity = capacity – cur_weight;

int b = remain_capacity;

//按单位重量的价值 递减序 装入物品

while(i<=n && w[i]<=remain_capacity)

{

remain_capacity-=w[i];

b+=p[i];

i++;

}

//装满背包

if( i<=n )

b+=p[i]/w[i]*remain_capacity; //准确的说这是一个上界，不是上确界

return b;

}

void dfs(int i)

{

//结束条件

if(i>n)

{

if(best_price >cur_price) //到此为止了，有用往后找了

{

for(int j=1;j<=n;j++)

best_solution[j] =x[j];

}

return ;

}

//搜索左子树，要当前结点

if(cur_weight+weght[i]< = capacity)

{

cur_solution[i] = 1;

cur_weight += weight[i];

cur_price += price[i];

dfs(i+1); cur_weight -= weight[i];

cur_price -= price[i];

}

//搜索右子树，不要当前结点,即数组中下一个结点

if(upper_bound(u+1)>best_price)

{ cur_solution[i]=0;

dfs(i+1);

}

}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/179547.html原文链接：https://javaforall.cn