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.

现在 James 需要最大限度地利用他现有的钱(900 美元)。也就是说，他可以购买任何元素，但剩余的钱要越少越好。在这种情况下，最好的结果将是:James 带来了 B、C、D 项，他的余额为 50 美元。

这很容易用文字解释，但是当为这种情况编写程序或编写算法时，情况就完全不同了。

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

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

算法应该:

• 能够处理商店中灵活的商品数量(不一定只需要 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

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