CODEWITHSUNDEEP
algorithmmathknapsack-problem
Nosfert
Nosfert

Reputation: 542

Algorithm optimal fill

To clarify We have a list of objects. Each object has a attribute Size and a attribute Value. We then have a limited space.

I want to know how to get the best mixture of objects (or none mixture) so that the values of objects that occupy the space has the highest potential value.

So the size is as important as the value. And the size and value is fixed for each object so I cant have half an object.

Example So we have Object A with Size 2 and Value 5 Object B with Size 3 and Value 8

We have a limited Space with it's Size of 10.

Placing the Objects in the space we can see that we can have two instances of Object A and two instances of Object B and thus getting a total value of 26.

I would like to have an method/function that takes an array of Objects and a Size and returns a array of objects that has the highest potential value.

Sorry for not making the question clear from the start, great feedback. Hopefully the updated question above will clarify what im trying to do.

Upvotes: 1

Views: 1011

Answers (2)

skY
skY

Reputation: 111

n : 0 1 2 3
space: 2 2 4 5
value: 3 7 2 9
s = 10

then maximum benefit you can achieve is 19 by including items 0,1 and 3 which has combined weight of 9.

 /* *   
 s = given limited space  
 n = current element  
 val = value array for each element  
 space = space occupied by each element  
 * */


 public int findMaximumBenefit(int s, int n, int [] val, int [] space)
{
    if (s == 0 || n == weight.length)
    {
        return 0;
    }

    // if this item's size is greater than space available
    // then this item cannot be included in the knapsack
    if (space[n] > s)
        return findMaximumBenefit(s, n+1, val, space);

    // Case1: maximum benefit possible by including current item in the knapsack
    int includeCaseBenefit = val[n] + findMaximumBenefit(s-space[n], n+1, val, space);

    // Case2: maximum benefit possible by excluding current item from the knapsack
    int excludeCaseBenefit = findMaximumBenefit(s, n+1, val, space);

    // return maximum of case1 and case2 values 
    return max(includeCaseBenefit, excludeCaseBenefit);
}

this function gives you maximum possible benefit with given space limit. Now if you also want to know which all items have been contributed to find maximum benefit then you can use below link http://www.ideserve.co.in/learn/dynamic-programming-0-1-knapsack-problem

Upvotes: 1

Hannes
Hannes

Reputation: 1208

First point I see is that the solution is not dependent on what number a value has. It is enough to just consider the values.

Given a set of values (e.g. {5, 8, 10, 15}) and a desired target value, you can use dynamic programming: 

def solve(values, target):
    # Try big values first to get smaller results.
    # Does not work in all cases.
    # values.sort(reverse=True)

    # Init an array with 0, -1, -1, ...
    added_to_reach = [None] * (target + 1)
    added_to_reach[0] = 0

    # Dynamically calculate if it is possible to
    # reach each value i up to target and store the
    # last added value in added_to_reach[i].
    for i in range(1, target + 1):
        for v in values:
            if i - v >= 0 and added_to_reach[i-v] is not None:
                added_to_reach[i] = v

    # Calculate the solution by going back.
    while added_to_reach[target] is None:
        target -= 1

    result = []
    while target > 0:
        result.append(added_to_reach[target])
        target -= added_to_reach[target]

    return result

print(solve([5, 10, 13, 14], 39))

The complexity is linear in target (exponential in its representation size) in the worst case. As we greedily select a value to try next, it could be good to try big values first, but it acutally is not (see example).

Upvotes: 1

Related Questions