Maximize solution: construction of sublists meeting limit

Question

Maximize solution: construction of sublists meeting limit

Navigation

#1 by (2 votes)
#2 by (0 votes)

7

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 these items that do not exceed the total value of 20D. In that case, the first set should offer me the items that its values are the best possible solution to reach the 20D.

I do not know if I'm being too confused, or prolix, in my problem. However, I need to fit performance and fulfillment of this requirement into this solution. I have already researched the backpack theorem and Ags to solve this problem, but I believe there is some simpler solution ...

Any suggestions?

java algoritmo

asked by anonymous 24.02.2014 / 18:22

2 answers

How to use git to organize my development, approval and production environment? R - download CVM data via POST method (package httr)

score 2 · Answer 1

You have a set of items and you 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 very similar to the knapsack problem :

Theknapsackproblem(Knapsackproblem)isacombinatorialoptimizationproblem.Thenameisgivenduetothemodelofasituationinwhichitisnecessarytofillabackpackwithobjectsofdifferentweightsandvalues.Thegoalistofillthebackpackwiththehighestpossiblevalue,notexceedingthemaximumweight.

Thedifferenceisthatinyourcasetheweightandthevaluearethesamething.Youhaveavaluelimit,butyouwanttomaximizethevalue.ThisproblemisNP-Complete,iethereisnoknownsolutiontocalculatetheoptimalsolutioninnon-exponentialtime.

Asimplesolutionistousethefollowingrecursivealgorithm:

# 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.

score 0 · Answer 2

0

I think what you are looking for is this:

link

If you want an exact value set at 20D, you should search SubSet Sum.

25.02.2014 / 20:49