6-25 0/1背包问题 （队列式广度优先搜索） 分数 25 作者 严宏 单位 中国民用航空飞行学院

6-25 0/1背包问题 （队列式广度优先搜索）
分数 25
作者 严宏
单位 中国民用航空飞行学院
有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个载重限制为W的背包。

设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么不选中要么选中一次，求取满足总重量不大于W并且具有最大价值的物品装入方案。

函数接口定义：
void EnQueue(NodeType e, queue &qu); //结点e是否进队qu以及相应处理
void bfs(); //广度优先搜索最优解

输入样例：
第一行是物品数目n和总重量限制W
之后n行分别是各个物品的重量和价值

3 30
16 45
15 25
15 25
输出样例：
物品最优装载方案得到最大总价值

50

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7621612
• 除此之外, 这篇博客: 利用高中知识求解最小二乘法中的 第二步，对w进行配方法，配成w的完全平方式 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• (b - (y1-wx1))² + (b - (y2-wx2))² +(b - (y3-wx3))² （式1）
  b = y’ - wx’ （式2）

  要让式1的结果最小，将式2带入式1中，式1转换为：
  ( y’- wx’- (y1-wx1))² + ( y’- wx’- (y2-wx2))² +…+ ( y’- wx’- (yn-wxn))² （式3）

  式3可以转换为：
  ( y’- wx’- y1+wx1))² + ( y’- wx’- y2+wx2))² +…+ ( y’- wx’- yn+wxn))²

  合并每个平方中的w，上式可转换为：
  (w(x1- x’) - (y1-y’))² + (w(x2- x’) - (y2-y’))² +…+(w(xn- x’) - (yn-y’))²

  展开上式：
  w²(x1-x’)² -2w(x1-x’)(y1-y’) +(y1-y’)² +
  w²(x2-x’)² -2w(x2-x’)(y2-y’) +(y2-y’)² +
  …
  w²(xn-x’)² -2w(xn-x’)(yn-y’) +(yn-y’)²

  合并包含w的项：
  w²[(x1-x’)² + (x2-x’)² +…+(xn-x’)² ] -
  2w[(x1-x’)(y1-y’) + (x2-x’)(y2-y’) +…+(xn-x’)(yn-y’)] +常数项

  将[(x1-x’)² + (x2-x’)² +…+(xn-x’)² ]定义为A
  将[(x1-x’)(y1-y’) + (x2-x’)(y2-y’) +…+(xn-x’)(yn-y’)]定义为B

  上式就可以转换为：
  W²*A -2W*B + 常数项

  将上式用配方法转换为完全平方式并合并成差平方的格式，上式就可以转换为：
  A(W-B/A)² + 常数项

  此时要使整个式子的结果最小，必须：
  W=B/A

  B = [(x1-x’)(y1-y’) + (x2-x’)(y2-y’) +…+(xn-x’)(yn-y’)]
  利用求和符号Σ可以将[(x1-x’)(y1-y’) + (x2-x’)(y2-y’) +…+(xn-x’)(yn-y’)]表示为：
  

  A=[(x1-x’)² + (x2-x’)² +…+(xn-x’)² ]，利用求和符号可以表示为：
  

  由w=B/A,因此w的结果就是：