ruby - Ruby でこの非 0-1 整数 Knapsack_Problem を解決する方法

Question

質問：

最小化x1+x2+...+xn

知られているk1*x1+k2*x2+...kn*xn = T

k1,k2,...,knおよびTは既知の整数であり、> 0

k1 > k2 > k3 > ... > kn

すべての x も整数で >= 0

すべての x を見つける

Rglpk と Glpk を使用しようとしていました。しかし、行列が 1 行しかない例が見つかりません。これは整数計画法ですか？そして、それは解決可能ですか？どうもありがとう。

---

私が書いたいくつかの Ruby コード:

ks = [33, 18, 15, 5, 3]
t = 999

problem = Rglpk::Problem.new
problem.name = "test"
problem.obj.dir = Rglpk::GLP_MIN

rows = problem.add_rows(1)
rows[0].name = "sum of x equals t"
rows[0].set_bounds(Rglpk::GLP_UP, t, t)

cols = problem.add_cols(ks.size)
ks.each_with_index do |k,index|
  cols[index].name = "k: #{k}"
  cols[index].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)
end

problem.obj.coefs = Array.new(ks.size, 1)

problem.set_matrix(ks)

problem.simplex
minimum_x_sum = problem.obj.get
xs = []
cols.each do |col|
  xs << col.get_prim
end
xs