背包问题

已知：假设背包最多能装的重量为4，现在有三种商品，分别有不同价值和重量。

问：怎样在能够使得装在背包中的商品价值最多？

算法实现

商品有:
              value  weight
gitar         1500     1
keyboard      3000     4
accordion     2000     3

#!/usr/bin/ruby

max_weight = 4
goods = [ [1500, 1], [3000, 4], [2000, 3] ]


matrix = Array.new(goods.size){Array.new(max_weight){0}}

def get_matrix(matrix, i, j)
  if i < 0
    return 0
  end
  matrix[i][j]
end

def up_cell(matrix, i, j)
  if matrix[i-1][j] == nil
    return 0
  end
  matrix[i-1][j]
end

puts "#"*60
puts "max_weight: #{max_weight}"
puts "goods:#{goods}"
puts  "#"*60
puts

0.upto(goods.size-1) { |i|
  0.upto(max_weight-1) { |j|
    cur_we = j + 1
    # can put
    if goods[i][1] < cur_we
      remain_weight = j - goods[i][1]
      # put in and package is full
      matrix[i][j] = goods[i][0] + get_matrix(matrix, i-1, remain_weight)
    elsif goods[i][1] == cur_we
      matrix[i][j] = goods[i][0]
    # can not
    else
      matrix[i][j] = up_cell(matrix, i, j)
    end
    # p matrix
  }
}

puts
p "result: #{matrix}"

puts "answer is: #{matrix[goods.size-1][max_weight-1]}"

可以调整变量goods增加新的商品，也可以调整背包重量max_weight，来满足不同的情况。现在的重量还没有考虑小数的情况。