Java优化算法

Question

我是编程新手，目前正面临建立优化算法的问题，我无法找到一个好的高效的解决方案来实现我当前面临的情况所期望的目标。就是这种情况：

假设现在詹姆斯有900美元，在一家商店中有4件商品的价格不同。

项目A：450美元

项目B：300美元

项目C：350美元

项目D：200美元

*每个项目的存货数量仅为一个。

现在，詹姆斯需要最大限度地利用自己现有的资金（900美元）。换句话说，他可以购买任何物品，但是剩余的钱需要尽可能少。在这种情况下，最好的结果将是：詹姆斯带来了项目B，C和D，他的剩余余额为50美元。

用语言解释很容易，但是针对这种情况进行编程或编写算法时，情况就完全不同了。

我曾尝试编写逻辑：将商品价格从低到高排序，然后从最低价格的商品中扣除900美元的货币余额，直到没有可以买到的商品为止，但是我意识到这种逻辑无法实现最大化使用金钱。例如，当将900美元的金额更改为800美元时，最好的情况是购买450美元和350美元的商品，剩余的为零，但是我的逻辑将购买300美元和200美元的商品，因为早期商品已分类。

因此，我在这里提出这个问题，以找出解决此情况的任何解决方案。我知道这可能是一个愚蠢的问题，但我确实尽我所能来学习和改进。

该算法应：

• 能够处理商店中灵活的项目数量（不必仅4个项目，可以多于或少于4个）和可变的开始预算（不需要900块钱，可以每次更改）。
• 每个产品只能购买一次。

*请为我提供参考，以从您的解决方案中学习。谢谢。

Answer 1

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

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

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