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美元，它可以改变everytime).

• Every产品只能购买一次。

。

*请向我提供参考，让我从你的解决方案中学习。谢谢。

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联机编译器上试用：

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

Answer 2

你可以通过递归来解决这个任务。当您有一个可以为给定预算选择最佳项目组合的方法时，按如下方式实现：

迭代项目和每个项目，检查它是否在预算范围内，如果是，从可用项目中删除它，并从预算中减去它的成本。然后，递归地询问剩余项目与剩余预算的最佳组合，并将其与当前项目相结合。检查结果的组合是否比前一个更好，并且只保持最好的组合。

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

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 3

解决办法是建立一本字典，把你可以花的所有钱的总数，以及最后一次购买是什么使你到达那里。然后拿出你找到的最大数量，然后把字典拿回来，找出你买的物品清单。

下面是一个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}))