0-1背包问题 回溯法

0-1背包问题回溯法

全栈程序员-站长 • 2026年3月26日下午9:22 • 未分类 • 阅读 2

0-1背包问题回溯法

② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：

1> x[i]=j；

方法1

#include 
    int n,c,bestp;//物品的个数，背包的容量，最大价值 int p[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况 void Backtrack(int i,int cp,int cw) { //cw当前包内物品重量，cp当前包内物品价值 int j; if(i>n)//回溯结束 { if(cp>bestp) { bestp=cp; for(i=0;i<=n;i++) bestx[i]=x[i]; } } else for(j=0;j<=1; j++) { x[i]=j; if(cw+x[i]*w[i]<=c) { cw+=w[i]*x[i]; cp+=p[i]*x[i]; Backtrack(i+1,cp,cw); cw-=w[i]*x[i]; cp-=p[i]*x[i]; } } } int main() { int i; bestp=0; printf("请输入物品个数和背包最大容量:\n"); scanf("%d%d",&n,&c); printf("请依次输入物品的价值:\n"); for(i=1;i<=n;i++) scanf("%d",&p[i]); printf("请依次输入物品的重量:\n"); for(i=1;i<=n;i++) scanf("%d",&w[i]); Backtrack(1,0,0); printf("最大价值为:\n"); printf("%d\n",bestp); printf("被选中的物品依次是(0表示未选中，1表示选中)\n"); for(i=1;i<=n;i++) printf("%d ",bestx[i]); printf("\n"); return 0; }

for(j=0;j<=1; ++j) // 枚举i所有可能的路径，

在满足限界函数和约束条件if(cw+x[i]*w[i]<=c)下，连续排列，直到碰壁，然后进行下一条路（另一个条件），进行下一次的遍历，直到结束，如图

(http://pic002.cnblogs.com/images/2011//51028.jpg)

最坏情况下有O（2n）个右儿子结点用限界函数，故计算0-1背包问题的回溯算法的时间复杂度为O(n2的n次方)，在搜索过程中的任何时刻，仅保留从开始结点到当前可扩展结点的路径，其空间需求为O（从开始结点起最长路径的长度）。所以，空间复杂度为O（n）

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176663.html原文链接：https://javaforall.net

0-1背包问题回溯法

关于作者

全栈程序员-站长

发表回复

0-1背包问题 回溯法

关于作者

全栈程序员-站长

相关推荐

python的进制转换器,Python进制转换[通俗易懂]

揭秘LangChain AI模型：性能对比，谁才是AI语言处理的佼佼者？

Apache tez_apache ii

Android学习——VAP源码

R语言——决策树模型

对接文心一言（ERNIE-Bot）的微信聊天机器人源码V2

发表回复

0-1背包问题回溯法