大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
解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);
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/179547.html原文链接：https://javaforall.net
