回溯法求0-1背包问题

《算法设计与》实验 学 号：   姓 名： 日 期：   得 分：       一、实验内容： 用回溯法求解0/1背包问题 注：给定 种物品和一个容量为 的背包，物品 的重量是 ，其价值为 ，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。 二、所用算法的基本思想及复杂度分析： 1.回溯法求解背包问题： 1） 基本思想： 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 2）复杂度分析： 回溯法求解0/1背包问题的时间复杂度为： 。 空间复杂度：有 个物品，即最多递归 层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为 。 2.以动态规划法验证： 1）基本思想： 令 表示在前 个物品中能够装入容量为 的背包中的物品的最大值，则可以得到如下动态函数： 按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第 个阶段。最后， 便是在容量为 的背包中装入 个物品时取得的最大价值。 2）复杂度分析： 动态规划法求解0/1背包问题的时间复杂度为： 。 三、源程序及注释： #include #include using namespace std; struct goods    //物品结构体 { int sign;    //物品序号 int w;    //物品重量 int v;    //物品价值 }a[100]; bool m(goods a,goods b) { return (a.v/a.w)>(b.v/b.w); } int max(int a,int b) { return an-1){ if(bestP0;i--) { if (V[i][j]>V[i-1][j]){ x[i-1]=1; j=j-a[i-1].w; } else    x[i-1]=0; } return V[n][C];    //返回背包取得的最大价值 } //测试以上算法的主函数 int main() { printf("物品种数n: "); scanf("%d",&n);    //输入物品种数 printf("背包容量C: "); scanf("%d",&C);    //输入背包容量 for (int i=0;i