CODEWITHSUNDEEP
java
oalsing
oalsing

Reputation: 100

Saving already calculated values

Basically I have a list of items and, which have parameters of size and value that needs to fit with a lot of other items in the best way, to reach the highest value possible but staying under a maxSize.

To explain the issue, see the following explanation.

Item 1: Size 1, Value 1;

Item 2: Size 2, Value 4:

Max Size: 11; Best solution: 1xItem1, 5xItem2.

But in this very case, the limit is higher and the items are many more. My problem is to find the best possible mix. So far I've created a algorithm that does this, but since the complexity is so bad, it only works with a few items.

I am basically trying every possible combination, which creates a lot of calculations on higher numbers of items. I am saving the path taken as a string (Item2->Item2->Item1->Item2...), until the total size is higher then the limit. If the value is higher then some other found value, it is saved as well as the string.

What I do want to do is the save all calculations already done, here is an example.

A -> A -> A -> A -> A

A -> B -> A -> A -> A

In the last case, it is not necessary to re-calculate A -> A -> A, and what I want to do is to save it away.

What would be the best way to do this?

Currently, my recursion looks something like this

recursion(Item item, int size, int value, String s){
  s += cust.getName() + "-";
if(value is bigger)
  bestMix = s



for(Item item : itemList){
        if(!(we break the limit){
            recursion(item, size + item.getSize(), value + item.getValue(), s);
        }
    }
}

What I want to do, is to fetch already calculated values when doing the recursion.

What would be the simplest and smartest way to do this in order to lower the time complexity?

Upvotes: 1

Views: 269

Answers (3)

oalsing
oalsing

Reputation: 100

As dasblinkenlight said, memoization is the way to go, but I decided to do something else.

I realized that my problem was identic to "the unbound knapsack problem" More information here: http://www.cs.rit.edu/~zjb/courses/800/lec7.pdf http://en.wikipedia.org/wiki/Knapsack_problem

Which I solved with dynamic programming. http://en.wikipedia.org/wiki/Dynamic_programming

This made my time complexity much better.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726579

What you are looking for is called memoization, a common algorithmic technique of the dynamic programming variety that lets you improve speed by reusing solutions to subproblems. A necessary condition for this technique is that the problem being solved had an optimal substructure, which your problem has.

Here is a way the memoization is commonly implemented: you add an extra parameter to your recursive routine, which contains a map of solutions to known subproblems. Parameters to each subproblem are encoded as a key to look up in the map of known solutions.

The first thing the memoized recursive solution does is constructing a key and running a lookup in the map of known solutions. If the answer is there, it is returned right away without recursing down any further. If the answer is not there, it is calculated in the regular way, and then placed in the map of solutions before returning from the recursive call.

Upvotes: 2

Joop Eggen
Joop Eggen

Reputation: 109557

Item 1 has a per size profit (double value/size( of 1/1. Item 2 has a larger per size profit of 4/2. So you should sort your itemList (with a Comparator) with Item 2 first. Then the first encountered solution can be the maximal one.

Another improvement would be to also have a int factor for every item, starting to try with the highest factor.

In general recursion has parameters for things done, and things to-do (candidates).

With recursion at every call one has a partial result. Caching on visiting the rest might be feasible but is more something for an already existing data structures like some tree structure.

Upvotes: 0

Related Questions