in reply to Proportional distribution of indivisible items

I'd say partition problem (optimization variant with N partitions, ie the worst kind) rather than Knapsack, but otherwise the conclusion is pretty much the same. This means that while finding the best solution is easy (test all combinations, keep the best one), doing so in reasonable time is worth 1 million. Your "intuitive winner" looks like a pretty good approximation.

For what I understand of neural networks, I don't think they are relevant for this kind of problems. This is neither extracting information (the data size of the output, ie an ordering of your elements, is the same as the input), nor a classification problem (an element isn't sent to a set according to its properties alone, but to the properties of all the elements in the input).

  • Comment on Re: Proportional distribution of indivisible items

Replies are listed 'Best First'.
Re^2: Proportional distribution of indivisible items
by anonymized user 468275 (Curate) on Aug 16, 2018 at 09:27 UTC
    Yes it does look like a partitioning problem but for reals not just integers. The best solution is indeed supposed to be something similar to a neural network, but so far the example solutions I found which build a tree and walk it (my earlier idea was to have N tree-walkers where N is also the number of workers when parallel processing of the jobs begin) seem to have errors in the method. My latest idea taken from various replies and munged/improved, is to start by putting the biggest five each in their own child process (that first step is obviously right though difficult to prove) and have each worker, on finishing a job, solve the remaining tree for what to take next. The dynamic solution of only 25 processes takes no time compared with the heavy jobs being performed.

    One world, one people

[reply]
      > My latest idea taken from various replies and munged/improved, is to start by putting the biggest five each in their own child process (that first step is obviously right though difficult to prove) 

      Probably because it's obviously wrong?

      5+5+2 =12

      3+3+3+3=12

      > have each worker, on finishing a job, solve the remaining tree for what to take next

      That's the best approach if you can avoid race conditions of two workers picking the same job.

      > it does look like a partitioning problem but for reals not just integers.

      All floats are effectively only integer approximations of real numbers. So?

      > The best solution is indeed supposed to be something similar to a neural network,

      By whom? Source?

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

[reply]
        kabocha (except this feature is disabled). So I'll give you an exercise - see if you can find where your post contradicts itself.

        update: hint: it isn't in your example supersets, in spite of the fact that they are a non-example.

        One world, one people

[reply]

In Section Seekers of Perl Wisdom