Note: The closer the sum of the prices are to max_price, the better

Initial data:

**max_price** = 11

[
  {
    id: 1,
    price: 5
  },
  {
    id: 2,
    price: 6
  },
  {
    id: 3,
    price: 6
  },
  {
    id: 4,
    price: 1
  },
  {
    id: 5,
    price: 3
  },
]

For instance, for the first time, we should return

[
  {
    id: 1,
    price: 5
  },
  {
    id: 2,
    price: 6
  }
]

because the sum of prices of these 2 elements is equal to or less than max_price.

But for the next time, we should return other random elements where their price sum is equal to or less than max_price

[
  {
    id: 3,
    price: 6
  },
  {
    id: 4,
    price: 1
  },
  {
    id: 5,
    price: 3
  }
]

Every time we should return an array with random elements where their sum is equal to or less than max_price.

How can we do that in ruby?

CodePudding user response：

As @Spickerman stated in his comment, this looks like the knapsack problem, and isn't language sensitive at all.

for a Ruby version, I played around a bit, to see how to get the pseudocode working, and I've come up with this as a possible solution for you:

Initialisation of your records:

@prices =
  [
    { id: 1, price: 3 },
    { id: 2, price: 6 },
    { id: 3, price: 6 },
    { id: 4, price: 1 },
    { id: 5, price: 5 }
  ]

# Define value[n, W]
@max_price = 11
@max_items = @prices.size

Defining the Ruby subprocedures, based on that Wiki page, one procedure to create the possibilities, one procedure to read the possibilities and return an index:

# Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
def put_recurse(i, j)
  if i.negative? || j.negative?
    @value[[i, j]] = 0
    return
  end

  put_recurse(i - 1, j) if @value[[i - 1, j]] == -1 # m[i-1, j] has not been calculated, we have to call function m
  return unless @prices.count > i

  if @prices[i][:price] > j # item cannot fit in the bag
    @value[[i, j]] = @value[[i - 1, j]]
  else
    put_recurse(i - 1, j - @prices[i][:price]) if @value[[i - 1, j - @prices[i][:price]]] == -1 # m[i-1,j-w[i]] has not been calculated, we have to call function m
    @value[[i, j]] = [@value[[i - 1, j]], @value[[i - 1, j - @prices[i][:price]]]   @prices[i][:price]].max
  end
end

def get_recurse(i, j)
  return if i.negative?

  if @value[[i, j]] > @value[[i - 1, j]]
    @ret << i
    get_recurse(i - 1, j - @prices[i][:price])
  else
    get_recurse(i - 1, j)
  end
end

procedure to run the previously defined procedures in a nice orderly fashion:

def knapsack(items, weights)
  # Initialize all value[i, j] = -1
  @value = {}
  @value.default = -1
  @ret = []

  # recurse through results
  put_recurse(items, weights)
  get_recurse(items, weights)
  @prices.values_at(*@ret).sort_by { |x| x[:id] }
end

Running the code to get your results:

knapsack(@max_items, @max_price)

CodePudding user response：

Just replying to these two points:

The closer the sum of the prices are to max_price, the better

Every time we should return an array with random elements where their sum is equal to or less than max_price.

One coarse approximation is to fill your basket with random items until you cannot put anymore items in it without exceeding max_price.

#!/usr/bin/env ruby

items = [
  { id: 1, price: 3 },
  { id: 2, price: 6 },
  { id: 3, price: 6 },
  { id: 4, price: 1 },
  { id: 5, price: 5 }
]

max_price = 11

basket_price = 0
basket = items.shuffle.select do |item|
  tmp_price = basket_price   item[:price]
  basket_price = tmp_price if tmp_price <= max_price
end

p basket