Maximize Solution: Sublist Construction Meeting Limit

Question

Having a set of n-values, I need to divide these items into subsets that do not exceed the value (sum of all items) stipulated and assure me that the formation of the set is as close as possible to the stipulated value.

For example, having a set of n-items that the total value is 100D, I want to create lists of those items that do not exceed the total value of 20D. In this case, the first set should offer me the items that their values is the best possible solution to achieve the 20D.

I don’t know if I’m being too confusing or prolific in my problem. However, I need to fit performance and fulfillment of this requirement in this solution. I have researched the backpack theorem and Ags for the solution of this problem, but I believe there is some solution but simple...

Any suggestions?

Answer 1

You have a set of items and that form a subset whose sum is less than X, so that it has the largest possible sum and has the largest possible number of items.

This problem is quite similar to knapsack problem:

The backpack problem (in English, Knapsack problem) is a combinatorial optimization problem. The name is given due to the model of a situation where it is necessary to fill a backpack with objects of different weights and values. The goal is to fill the backpack with the highest possible value, not exceeding the maximum weight.

The difference is that in your case weight and value are the same thing. You have a value limit, but you want to maximize value. This problem is NP-Complete, that is: there is no known solution to calculate the optimal solution in non-exportive time.

A simple solution is to use the following recursive algorithm:

# Encontre o maior conjunto com os n primeiros itens de set tal que seja menor que o limit
def bestsubset(set, n, limit)
    if n == 0
        # O melhor conjunto com zero itens é o conjunto vazio
        return []
    end

    if set[n-1] > limit
        # Se o ultimo for menor que o limite, exclua ele
        return bestsubset(set, n-1, limit)
    end

    # a = melhor conjunto excluindo o ultimo item
    # b = melhor conjunto incluindo o ultimo item
    a = bestsubset(set, n-1, limit)
    b = bestsubset(set, n-1, limit-set[n-1]) + [set[n-1]]

    # computar as somas
    sum_a = a.reduce(:+) || 0
    sum_b = b.reduce(:+) || 0

    if sum_a > sum_b
        return a
    else
        # se soma deu igual, retorna o que tem mais itens
        return b
    end
end

.

p bestsubset([3,1,1,1,2,7], 6, 5)  #=> [1, 1, 1, 2]

I wrote in Ruby, but you can adapt to any language.

Answer 2

I think what you’re looking for is this:

http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane.html

If you want an exact 20D value set, you should search for Subset Sum.