【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《0-1背包问题代码(可执行)》，欢迎阅读！
word格式-可编辑-感谢下载支持 在这里再简单写一下问题要求： 给定n中物品和一个容量为c的背包，物品i的重量为Wi,其价值为Vi,0-1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包的物品的价值为最大。 1.题目分析： 考虑到每种物品只有2 种选择，即装入背包或不装入背包，并且物品数和背包容量已给定，要计算装入背包物品的最大价值和最优装入方案，可用回溯法搜索子集树的算法进行求解。 2.算法设计： a. 物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品的价值和重量，用 x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案； b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深 度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前 最优总价值）： ① 若i >n，则算法搜索到一个叶结点，判断当前总价值是否最优： 1> 若cp>bestp，更新当前最优总价值为当前总价值（即bestp=cp），更新 装载方案（即bestx[i]=x[i]( 1≤i≤n)）； ② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）： 1> x[i]=j； 2> 若总重量不大于背包容量（即cw+x[i]*w[i]<=c），则更新当前总价 br=""> 值和总重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）, 对物品i+1调用递归函 数Backtrack(i+1,cp,cw) 继续进行装载； 3> 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量 （即 cw-=w[i]*x[i],cp-=p[i]*x[i]）； 4> 当j>1时，for循环结束； ③ 当i=1时，若已测试完所有装载方案，外层调用就全部结束； c. 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。 #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]; word格式-可编辑-感谢下载支持 } } 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",&c); printf("请输入物品个数:\n"); scanf("%d",&n); printf("请依次输入物品的重量:\n"); for(i=1;i<=n;i++) scanf("%d",&w[i]); printf("请依次输入物品的价值:\n"); for(i=1;i<=n;i++) scanf("%d",&p[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; } 本文来源：https://www.dywdw.cn/b64f120cc181e53a580216fc700abb68a982ad61.html
下载此文档
搜索文档
阅读：
文档下载
2022-07-14
