CODEWITHSUNDEEP
algorithm
Ildar
Ildar

Reputation: 184

algorithm to map weighted objects to their amount

need algorithm to map weighted objects to their amount and need to make amount minimal for each object with keeping ratio between weights

example 1:

input: object1: 40, object2: 60, object3: 80 
output: object1: 2, object2: 3, object3: 4

this can be solved by dividing object weight with gcd of weights of all objects

example 2:

input: object1: 3, object2: 15
output: object1: 1, object2: 5

example 3:

input: object1: 13, object2: 97, object3: 20
output: object1: 1, object2: 7, object3: 2

example 4:

input: object1: 1, object2: 17, object3: 97
output: object1: 0, object2: 1, object3: 5

gcd is not applicable for example 3 and 4, what's the algorithm can be used, is there any idea?

limitations: range of weights 0-99, maximum sum of all amounts is 32

Upvotes: 3

Views: 107

Answers (1)

Dave
Dave

Reputation: 9065

As I mentioned in comments, dividing by the GCD is the best you can do if you need integers that exactly preserve the ratio.

For floats that are very close to the ratio, divide everything by the min.

Ruby example:

def f(weights)
  min_wt = weights.min
  ans = []
  weights.each do |wt|
    ans.append(wt.to_f/min_wt)
  end
  return ans
end

> f([40, 60, 80])
=> [1.0, 1.5, 2.0]

> f([13, 97, 20])
=> [1.0, 7.461538461538462, 1.5384615384615385]

Alternate approach to get integers: Check every scaling factor in your range (final sum 1-32). I'm taking 1 as the floor for each integer since dividing by 0 is undefined.

Ruby code (not beautifully written):

def f(unsorted_weights)
  weights = unsorted_weights.sort!
  orig_sum_of_wts = weights.sum
  best_error = Float::INFINITY
  best_sum_of_wts = 0
  1.upto(32) do |new_sum_of_wts|
    error = 0.0
    new_wts = []
    0.upto(weights.length - 1) do |i|
      new_wts[i] = [1, weights[i] * new_sum_of_wts / orig_sum_of_wts].max
    end
    0.upto(weights.length - 2) do |i|
      new_wt_i = weights[i] * new_sum_of_wts / orig_sum_of_wts
      (i+1).upto(weights.length - 1) do |j|
        new_wt_j = weights[j] * new_sum_of_wts / orig_sum_of_wts
        error += (new_wts[j].to_f / [new_wts[i], 1.0].max - weights[j].to_f / [weights[i], 1.0].max).abs 
        
      end
      if error < best_error
        best_sum_of_wts = new_sum_of_wts
        best_error = error
      end
    end
  end
  ans = []
  0.upto(weights.length - 1) do |i|
    ans.append([1, weights[i] * best_sum_of_wts / orig_sum_of_wts].max)
  end
  puts "#{ans.to_s}"
end

Results:

> f([40, 60, 80])
[2, 3, 4]

> f([40, 60])
[2, 3]

> f([13, 97, 20])
[2, 3, 15]

> f([1, 17, 97])
[1, 4, 26]

For 13, 20, 97, I get 2,3,15 vs your 1,2,7.

Ratios: 20/13 = 1.538,  3/2 = 1.500, 2/1 = 2.000
        97/13 = 7.462, 15/2 = 7.500, 7/1 = 7.000
        97/20 = 4.850, 15/3 = 5.000, 7/2 = 3.500

Cumulative error for 2,3,15: 0.038 + 0.038 + 0.150 = 0.226
Cumulative error for 1,2,7:  0.038 + 0.462 + 1.350 = 2.274

Upvotes: 2

Related Questions