2023年8月1日发(作者：)

回溯法解决0-1背包问题问题描述：　　有n件物品和⼀个容量为c的背包。第i件物品的价值是v[i]，重量是w[i]。求解将哪些物品装⼊背包可使价值总和最⼤。所谓01背包，表⽰每⼀个物品只有⼀个，要么装⼊，要么不装⼊。回溯法：　　01背包属于找最优解问题，⽤回溯法需要构造解的⼦集树。在搜索状态空间树时，只要左⼦节点是可⼀个可⾏结点，搜索就进⼊其左⼦树。对于右⼦树时，先计算上界函数，以判断是否将其减去，剪枝啦啦！ 上界函数bound():当前价值cw+剩余容量可容纳的最⼤价值<=当前最优价值bestp。 为了更好地计算和运⽤上界函数剪枝，选择先将物品按照其单位重量价值从⼤到⼩排序，此后就按照顺序考虑各个物品。

#include #include int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装⼊//按单位价值排序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]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) { leftw-=w[i]; b+=v[i]; i++; } if(i<=n) b+=v[i]/w[i]*leftw; return b;}int main(){ int i; printf("请输⼊物品的数量和容量："); scanf("%d %lf",&n,&c); printf("请输⼊物品的重量和价值："); for(i=1;i<=n;i++) { printf("第%d个物品的重量：",i); scanf("%lf",&w[i]); printf("价值是："); scanf("%lf",&v[i]); order[i]=i; } knapsack(); backtrack(1); printf("最有价值为：%lfn",bestp); printf("需要装⼊的物品编号是："); for(i=1;i<=n;i++) { if(put[i]==1) printf("%d ",order[i]); } return 0;}

时间复杂度分析：　　上界函数bound()需要O(n)时间，在最坏的情况下有O(2^n)个右⼦结点需要计算上界，回溯算法backtrack需要的计算时间为O(n2^n)

2023年8月1日发(作者：)

回溯法解决0-1背包问题问题描述：　　有n件物品和⼀个容量为c的背包。第i件物品的价值是v[i]，重量是w[i]。求解将哪些物品装⼊背包可使价值总和最⼤。所谓01背包，表⽰每⼀个物品只有⼀个，要么装⼊，要么不装⼊。回溯法：　　01背包属于找最优解问题，⽤回溯法需要构造解的⼦集树。在搜索状态空间树时，只要左⼦节点是可⼀个可⾏结点，搜索就进⼊其左⼦树。对于右⼦树时，先计算上界函数，以判断是否将其减去，剪枝啦啦！ 上界函数bound():当前价值cw+剩余容量可容纳的最⼤价值<=当前最优价值bestp。 为了更好地计算和运⽤上界函数剪枝，选择先将物品按照其单位重量价值从⼤到⼩排序，此后就按照顺序考虑各个物品。

#include #include int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装⼊//按单位价值排序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]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) { leftw-=w[i]; b+=v[i]; i++; } if(i<=n) b+=v[i]/w[i]*leftw; return b;}int main(){ int i; printf("请输⼊物品的数量和容量："); scanf("%d %lf",&n,&c); printf("请输⼊物品的重量和价值："); for(i=1;i<=n;i++) { printf("第%d个物品的重量：",i); scanf("%lf",&w[i]); printf("价值是："); scanf("%lf",&v[i]); order[i]=i; } knapsack(); backtrack(1); printf("最有价值为：%lfn",bestp); printf("需要装⼊的物品编号是："); for(i=1;i<=n;i++) { if(put[i]==1) printf("%d ",order[i]); } return 0;}

时间复杂度分析：　　上界函数bound()需要O(n)时间，在最坏的情况下有O(2^n)个右⼦结点需要计算上界，回溯算法backtrack需要的计算时间为O(n2^n)