Java 优化算法

Question

我是编程新手，目前我面临构建优化算法的问题，我无法找到一个好的、有效的解决方案来实现我当前面临的场景的预期。是这样的：

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.

现在詹姆斯需要最大限度地利用他目前的钱（900 美元）。也就是说，他可以购买任何物品，但剩余的钱要越少越好。这样的话，最好的结果就是：James带了B、C、D，他的余额是50块。

用文字解释起来很容易，但是对于这种情况进行编程或编写算法时，情况就完全不同了。

我试过写逻辑：将商品价格从低到高排序，然后从价格最低的商品中扣除余额900元，直到没有余额的商品为止可以买，但是我意识到这个逻辑并不能实现金钱的最大化利用。比如900块变成800块，最好的情况是用450块和350块买东西，剩下的会是0，但是我的逻辑是买300块和200块的东西，因为排序早.

因此，我在这里问这个问题是为了找出处理这种情况的任何解决方案。我知道这可能是一个愚蠢的问题，但我真的尽力学习和提高。

算法应该：

能够处理灵活的店内商品数量（不一定只需要 4 件商品，可以多于或少于 4 件）和可变的起始预算（不需要 900 美元，每次都可以改变）。
每件商品限购一次。

*请提供参考，让我学习您的解决方案。谢谢。

Answer 1

解决方案是建立一个字典，包含您可能花费的所有总金额，以及最后一次购买是什么让您到达那里。然后取你找到的最大金额，然后在字典中查找你购买的物品列表。

这是一个 Python 解决方案：

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}))

Answer 2

对于那些正在关注这个问题的人，我找到了这个问题的解决方案：

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
        }
    }
}

*** 复制代码并在 Java 在线编译器上尝试：

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

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

*** 如果您发现任何问题或更好的方法来最大化数据传输效率，请改进或更正我的答案。谢谢。

Answer 3

你可以通过递归来解决这个问题。如果您有一种方法可以 select 给定预算的最佳项目组合，请按如下方式实现它：

遍历项目并为每个项目检查它是否在预算内，如果在预算内，则将其从可用项目中删除并从预算中减去其成本。然后，递归地询问剩余项目与剩余预算的最佳组合，并将其与当前项目组合。检查生成的组合是否比前一个更好，只保留最好的。

这可以通过使用按价格排序的项目列表来优化，这允许在所有剩余项目都比我们当前的预算更昂贵时停止迭代。有了列表，剩下的项目可以通过索引来表达，而不需要创建新的集合。我们不需要考虑当前项目之前的项目，因为这会导致我们之前已经检查过的组合：

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;
    }
}

这个可以这样用

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 4

你可以通过先计算所有的可能性然后对它们进行排序来解决这个问题。如果你能发现一个有趣的规则，找到所有的可能性并不那么复杂。举个例子：

   a
=======
  [a]

如果您只有一个输入 a，唯一可能的结果是 [a]。

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

如果您输入 a, b，则有 3 种可能的结果：[a], [b], [a, b]。

这是我们发现规则 1 的地方：单个元素 ([a]) 的可能性是 a, b 中可能性的子集。或广义：

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

让我们看看这是否适用于 a, b, c:

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

您可以针对更大的输入验证这一点，但它始终成立。如果你从长远来看，这一切都是有道理的。潜在n的所有组合将是：n-1的所有组合+更多。

不过这里还有一个规则比较有意思

如果你有这样的输入：

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

你可以创建一个算法来计算下一个。首先创建前一个的副本（因为上面的规则）：

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

对于第一行，您只需添加“最后一个”下一个字母。由于下一个是 a, b, c，所以您需要添加到第一行的是：c:

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

对于第二行，您使用前一行（减去添加的 c），附加“最后一个”下一个字母并将其插入。即：

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

一些 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

对于最后一行，我们只需添加所有“下一个”(a, b, c):

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

使用上面相同的逻辑，您可以计算 a, b, c, d 的结果：

先复制：

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

添加d:

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

 [d]

取上一行并追加：

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

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

同样，获取前一行并追加（记住：“除了添加的行之外”）：

                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]

最后一个：

                    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]

如果你明白上面发生了什么，那就是写代码了。我所做的唯一更改是不添加我已经知道将无法通过 max 检查的元素。在这里，它看起来很复杂，但实际上它相当微不足道（除了一些边缘情况外）：

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;
}

Java 优化算法

Java Optimization Algorithm

java

algorithm

optimization

knapsack-problem