Java Optimization Algorithm

Question

I'm new in programming, currently I'm facing an issue to build an algorithm for optimisation, I can't figure out a good and efficient solution to achieve what I'm expected for my current facing scenario. This is the case:

Assume now James have 900 bucks and there are 4 items in a shop in different price.

item A: 450 bucks

item B: 300 bucks

item C: 350 bucks

item D: 200 bucks

*stock amount of each item is one only.

Now James need to maximize the use of his current money (900 bucks). In other words, he can buy any items but the remaining money need to be as less as possible. In this case, the best result will be: James brought item B, C and D, his remaining balance will be 50 bucks.

It's easy to explain in word, but when come to program or write the algorithm for this case, it's totally different story.

I had tried to write the logic: sort the item price from low to high, then deduct the money balance 900 bucks from the lowest price item until no item that the balance can be buy, but I realised this logic not able to achieve maximize the use of money. For instance, when the amount of 900 bucks are changed to 800 bucks, the best case is buy item with 450 and 350 bucks, where remaining will be zero, but my logic will buy items with 300 and 200 bucks due to the early items sorted.

Thus, I'm asking this question in here to find out any solution to handle this scenario. I know this might be a stupid question, but I'm really try my best to learn and improve.

The algorithm should:

• Able to handle flexible number of items in shop (Not necessary 4 items only, can be more or less than 4) and changeable starting budget (Not necessary 900 bucks, it can be change everytime).
• Every product can be purchase one time only.

*Please provide reference for me to learn from your solution. Thank you.

Answer 1

you can solve this by computing all the possibilities first and then just sort them. Finding all the possibilities is not that complicated if you can spot an interesting rule. Let's take an example:

   a
=======
  [a]

If you have a single input a, the only possible result is [a].

     a, b
==============
 [a]  [a, b]
 [b]

If you have an input as a, b, there are 3 possible results: [a], [b], [a, b].

This is where we spot rule 1 : the possibilities of that single element ([a]) are a subset of possibilities in a, b. Or generalized:

all the possibilities from the previous result are going to be contained in the current one.

Let's see if that holds true for a, b, c:

     a, b                              a, b, c
==================         =============================
  --------------              -------------
 | [a]  [a, b]  |            | [a]  [a, b] |
 | [b]          |            | [b]         |
 |--------------|            |-------------|  [a, b, c]
                               [c]  [a, c]
                                    [b, c] 

You can verify this for much larger inputs, but it always holds true. And if you look in perspective, this all makes sense. All combinations of a potential n will be : all combinations of n-1 + some more.

---

But there is another rule here that is more interesting.

If you have such an input:

     a, b
==============
 [a]  [a, b]
 [b]

you can create an algorithm on how to compute the next one. First of all create a copy of the previous one (because of the rule above):

    a, b, c
==============
 [a]  [a, b]
 [b]

For the first row, all you need to add is the "last" next letter. Since the next one is going to a, b, c, all you need to add to the first row is : c:

    a, b, c
==============
 [a]  [a, b]
 [b]
 [c]

For the second row, you take the previous row (minus the c that was added), append the "last" next letter and insert it. That is :

      a, b, c
===================
 [a] <-|    [a, b]
 [b]   |->  [a, c]  <-- "a" came from the previous row, "c" was added as the last one
 [c]   

Some for b:

      a, b, c
===================
 [a]        [a, b]
 [b] <-|    [a, c]  
 [c]   |->  [b, c] <-- "b" came from the previous row, "c" then added as the last one

For the last row, we simply add all the "next one" (a, b, c):

            a, b, c
=================================
 [a]        [a, b]
 [b]        [a, c]     [a, b, c]
 [c]        [b, c]

With the same logic above, you can compute the result for a, b, c, d:

Copy first:

            a, b, c, d
=================================
 [a]        [a, b]
 [b]        [a, c]     [a, b, c]
 [c]        [b, c]

Add d:

            a, b, c, d
=================================
 [a]        [a, b]
 [b]        [a, c]     [a, b, c]
 [c]        [b, c]

 [d]

Take the previous row and append:

            a, b, c, d
=================================
 [a]        [a, b]
 [b]        [a, c]     [a, b, c]
 [c]        [b, c]

 [d]        [a, d]
            [b, d]
            [c, d]

Again, take the previous row and append (remember that: "besides the one that were added"):

                a, b, c, d
=================================
 [a]        [a, b]
 [b]        [a, c]     [a, b, c]
 [c]        [b, c]     [a, b, d]  <--- [a, b] + [d]
 [d]        [a, d]     [a, c, d]  <--- [a, c] + [d]
            [b, d]     [b, c, d]  <--- [b, c] + [d]
            [c, d] 

And the last one:

                    a, b, c, d
=================================================
 [a]        [a, b]
 [b]        [a, c]     [a, b, c]
 [c]        [b, c]     [a, b, d]  
 [d]        [a, d]     [a, c, d]   [a, b, c, d]
            [b, d]     [b, c, d] 
            [c, d] 

---

If you understand what happens above, it's all about writing the code. The only change I am making is not add elements that I already know will fail the check against max. And here it is, it looks complicated, but in reality it is fairly trivial (with some exception of some edge cases):

static List<String> partitions(List<Choice> all, int max) {

    ArrayList<ArrayList<ArrayList<Choice>>> previousResult = new ArrayList<>();
    ArrayList<ArrayList<ArrayList<Choice>>> currentResult = new ArrayList<>();

    int i = 0;
    for(;i<all.size();++i) {
        // add the first element
        Choice current = all.get(i);
        if(currentResult.isEmpty()) {
            if(less(List.of(current), max)) {
                // looks complicated, but all it does is adds a single element in the first index
                ArrayList<Choice> inner = new ArrayList<>();
                inner.add(current);
                ArrayList<ArrayList<Choice>> in = new ArrayList<>();
                in.add(inner);
                currentResult.add(in);
                previousResult.add(in);
            }
        } else {
            if(less(List.of(current), max)) {
                ArrayList<Choice> element = new ArrayList<>();
                element.add(current);
                currentResult.get(0).add(element);
            }
            if(currentResult.size() > 1) {
                for(int j=0;j<i-1;++j) {
                    if(j < previousResult.size()) {
                        ArrayList<ArrayList<Choice>> p = previousResult.get(j);
                        for(int d=0;d<=p.size()-1;++d){
                            ArrayList<Choice> copy = new ArrayList<>(p.get(d));
                            copy.add(all.get(i));
                            if(less(copy, max)){
                                currentResult.get(j).add(copy);
                            }
                        }
                    }

                }
            }

            // add tail if possible
            ArrayList<ArrayList<Choice>> tail = new ArrayList<>();
            ArrayList<Choice> t = new ArrayList<>(all.subList(0, i + 1));
            if(less(t, max)) {
                tail.add(t);
                currentResult.add(tail);
            }

            if(currentResult.size() == 1) {
                ArrayList<Choice> l = currentResult.get(0).stream().flatMap(List::stream).collect(Collectors.toCollection(ArrayList::new));
                if(less(l, max)) {
                    tail.add(l);
                    currentResult.add(tail);
                }
            }

            // smart copy here
            previousResult = copy(previousResult, currentResult);
        }

    }

    return
        currentResult.stream()
                     .flatMap(List::stream)
                     .map(list -> {
                            int sum = list.stream().mapToInt(Choice::getCost).sum();
                            List<String> l = list.stream().map(Choice::getKey).collect(Collectors.toList());
                            return new AbstractMap.SimpleEntry<>(sum, l);
                     })
                     .sorted(Map.Entry.<Integer, List<String>>comparingByKey().reversed())
                     .filter(x -> x.getKey() <= max)
                     .map(Map.Entry::getValue)
                     .findFirst()
                     .orElse(List.of());
}

private static ArrayList<ArrayList<ArrayList<Choice>>> copy(ArrayList<ArrayList<ArrayList<Choice>>> previousResult, ArrayList<ArrayList<ArrayList<Choice>>> currentResult) {
    return currentResult.stream()
                 .map(x -> x.stream().map(y -> (ArrayList<Choice>)y.clone()).collect(Collectors.toCollection(ArrayList::new)))
                 .collect(Collectors.toCollection(ArrayList::new));

}

private static boolean less(List<Choice> in, int max) {
    return in.stream().mapToInt(Choice::getCost).sum() <= max;
}

Answer 2

You can solve the task via recursion. When you have a method which can select the best combination of items for a given budget, implement it as follows:

Iterate over the items and for each item, check whether it is within the budget and if so, remove it from the available items and subtract its costs from the budget. Then, ask recursively for the best combination of the remaining items with the remaining budget and combine it with your current item. Check whether the resulting combination is better than the previous one and only keep the best.

This can be optimized by using a list of items sorted by price, which allows to stop iterating once all remaining items are more costly than our current budget. With a list, the remaining items can be expressed via index, without the need to create new collections. We don’t need to consider items prior to the current one, as that would result in combinations we’ve already checked before:

public static Set<String> select(Map<String,Integer> available, int budget) {
    List<Map.Entry<String,Integer>> temp = new ArrayList<>(available.entrySet());
    temp.sort(Map.Entry.comparingByValue());
    Choice c = selectImpl(temp, 0, budget);
    return c == null? Collections.emptySet(): c.items;
}
private static Choice selectImpl(
    List<Map.Entry<String, Integer>> availTemp, int start, int budget) {
    Choice c = null;
    for(int ix = start; ix < availTemp.size(); ix++) {
        Map.Entry<String, Integer> e = availTemp.get(ix);
        if(e.getValue() > budget) return c;
        Choice sub;
        int cost = e.getValue(), remaining = budget - cost;
        if(remaining == 0) return new Choice(e.getKey(), budget);
        sub = selectImpl(availTemp, ix + 1, remaining);
        if(c == null || c.cost < (sub == null? cost: sub.cost + cost))
            c = sub == null? new Choice(e.getKey(),e.getValue()): sub.add(e.getKey(),cost);
    }
    return c;
}
private static final class Choice {
    final Set<String> items;
    int cost;

    Choice(String key, int c) {
        items = new HashSet<>();
        items.add(key);
        cost = c;
    }
    Choice add(String key, int c) {
        items.add(key);
        cost += c;
        return this;
    }
}

This can be used like

Map<String,Integer> available = Map.of(
    "Item A", 450, "item B", 300, "Item C", 350, "item D", 200);
int budget = 900;
Set<String> picked = select(available, budget);
System.out.println("With "+budget+ ", buy "+picked
    +", consuming "+picked.stream().mapToInt(available::get).sum());

Answer 3

For those who are following this question, I've found the solution for this question:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.Map.Entry;
import java.util.LinkedHashMap;
import java.util.Iterator;

public class SumSet {
    static Map<Integer, ArrayList<Integer>> handleAllSumPossibilities(ArrayList<Integer> itemList, int balance, ArrayList<Integer> combination, Map<Integer, ArrayList<Integer>> qualifyItemsCombination) {

        System.out.println("COMBINATION FOR TEST: "+combination);

       int sum = 0; 
       Integer remain=null; 


       for (int x: combination){ sum += x;}; 

       if (sum <= balance && sum != 0){
            remain=(balance - sum);

            qualifyItemsCombination.put(remain,combination);
            System.out.println("ADD COMBINATION TO MAP: "+combination+"  CURRENT QUALIFIED COMBINATION: "+qualifyItemsCombination);
       }else{
            System.out.println("IGNORE COMBINATION: "+combination+"  NOT QUALIFY, THE COMBINATION IS EXCEEDED THE BALANCE");
       }
            System.out.println("_____________________________");


       for(int i=0;i<itemList.size();i++) {
             ArrayList<Integer> remainingItems = new ArrayList<Integer>();

             int pointingItem = itemList.get(i); 
             for (int j=i+1; j<itemList.size();j++) remainingItems.add(itemList.get(j));

             ArrayList<Integer> combinationRecord = new ArrayList<Integer>(combination);

             combinationRecord.add(pointingItem);

             Map<Integer, ArrayList<Integer>> retrievedItemsCombination = handleAllSumPossibilities( remainingItems, balance, combinationRecord, qualifyItemsCombination);
             qualifyItemsCombination = retrievedItemsCombination;

       }
            return qualifyItemsCombination;
    }



    static Map<Integer, ArrayList<Integer>> findBestCombination(ArrayList<Integer> itemList, int balance) {

        Map<Integer, ArrayList<Integer>> qualifyItemsCombination;
        qualifyItemsCombination = handleAllSumPossibilities(itemList,balance,new ArrayList<Integer>(),new HashMap<>());

        System.out.println("THE FINAL QUALIFIED COMBINATION: "+qualifyItemsCombination);

        //sort the key (remaining balance)
        List<Entry< Integer, ArrayList<Integer>>> qualifyItemsCombinationList = new ArrayList<>(qualifyItemsCombination.entrySet());
        qualifyItemsCombinationList.sort(Entry.comparingByKey());

        //place the sort result
        Map<Integer, ArrayList<Integer>> sortedResult = new LinkedHashMap<>();
        for (Entry<Integer, ArrayList<Integer>> entry : qualifyItemsCombinationList) {
            sortedResult.put(entry.getKey(), entry.getValue());
        }
        System.out.println("QUALIFIED COMBINATION AFTER SORTED: "+sortedResult);

        //iterate to get the first combination = the combination with lesser remaining.
        Map.Entry<Integer, ArrayList<Integer>> entry = sortedResult.entrySet().iterator().next();
        Integer getMapKey = entry.getKey();
        ArrayList<Integer> getMapValue=entry.getValue();

        //remove all the combination that contains the remaining(key)
        //different to the lesser remaining
        //the reason of doing this is to filter the combinations and ensure the map only left the combinations with the lesser remaining
        //since it might contains more than one combination are having the lesser remaining
        sortedResult.entrySet().removeIf(key -> key.getKey() != getMapKey);
        System.out.println("THE COMBINATION WITH LESSER BALANCE: "+sortedResult);

        return sortedResult;
    }



    public static void main(String args[]) {
        ArrayList<Integer> itemList = new ArrayList<>();
        itemList.add(450);
        itemList.add(350);
        itemList.add(300);
        itemList.add(200);

        int balance = 900;

        Map<Integer, ArrayList<Integer>> returnResult;
        returnResult = findBestCombination(itemList,balance);

        //Iterate to display all the combination with lesser balance remaining
        Iterator it = returnResult.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry)it.next();
            System.out.println("THE LESSER REMAINING: "+pair.getKey() + ", THE COMBINATION TO ACHIVE THIS: " + pair.getValue());   
            it.remove(); // avoid concurrent modification exception
        }
    }
}

*** Copy the code and try it on the Java online compiler:

https://www.jdoodle.com/online-java-compiler/

https://www.tutorialspoint.com/compile_java_online.php

*** Do improve or correct my answer, if you found any problem or better way to maximize the data delivery efficiency. Thank you.

Answer 4

The solution is to build up a dictionary of all of the total amounts of money you could have spent, and what the last purchase was that got you there. Then take the largest amount that you find, and walk the dictionary back to find the list of items that you bought.

Here is a Python solution that does this:

def optimal_buy (money, item_price):
    best = 0
    last_buy = {0: None}

    for item, price in item_price.iteritems():
        # Make a copy before altering the dictionary.
        prev_spent = [k for k in last_buy.keys()]
        for spent in prev_spent:
            next_spent = spent + price
            if next_spent <= money and next_spent not in last_buy:
                last_buy[next_spent] = item
                if best < next_spent:
                    best = next_spent

    answer = []
    while 0 < best:
        item = last_buy[best]
        answer.append(item)
        best = best - item_price[item]

    return sorted(answer)


print(optimal_buy(900, {'A': 450, 'B': 300, 'C': 350, 'D': 200}))