登录
首页 » C++ » 12-01bag

12-01bag

于 2012-12-29 发布 文件大小:306KB
0 32
下载积分: 1 下载次数: 6

代码说明:

  01背包问题 问题陈述:给定n种物品和一背包,物品i的重量是wi,其价值为vi,背包的容量为C。合理选择物品装入背包,使得装入背包中物品的总价值最大。在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。 问题分析:0 1背包问题是一个子集选取问题,适合于用子集树表示0 1背包问题的解空间。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解时才进入右子树搜索;否则将右子树剪去。 (01 knapsack problem problem statement: given n kinds of items, and a backpack, the weight of the items i wi, the value of vi, backpack capacity C. Reasonable choice items into a backpack, making the total value of the items loaded backpack. Each item i select items loaded backpack, there are only two choices that loaded backpack or loaded backpack. Items i can not be loaded into a backpack many times not only loaded items i. The problem analysis: 01 knapsack problem is a selected subset of the problem and suitable for the tree represents a subset of the solution space of 01 knapsack problem. Search solution space tree, as long as its left son node is a feasible node, the search into the left subtree, right subtree may contain only into the right subtree search the optimal solution Otherwise, the right subtree cut.)

下载说明:请别用迅雷下载,失败请重下,重下不扣分!

发表评论

0 个回复

  • 696518资源总数
  • 104224会员总数
  • 54今日下载