• 输入
    • n个物品组成集合O , 每个商品有两个属性vi 和pi , 分别表示体积和价格
    • 背包容量为C
  • 输出
    • 求解一个商品子集 S⊆O ,
      • 目标 : max ∑pi
      • 约束条件 : s.t. ∑vi <= C


一 . 蛮力枚举

  • 枚举所有可能 :
    • 首先枚举所有情况 , 共 Cn,1 + ….. + Cn,n = 2-1 种情况
    • 然后将所有情况中体积超出的情况删除
    • 然后在剩余情况中找到价值最大的组合 , 就是最优解
  • 实现方法