代币兑换实施问题 (Java)

Question

我运行在尝试使用 DP 解决这个经典问题时遇到了一个实现问题。问题是给出一组硬币，return给出最少硬币数量的最佳方法。

import java.util.*;

class coin4
{
    static int coin_values[] = {16, 4, 8};
    static Map<Integer, Vector<Integer>> memo;
    static Vector<Integer> give(int n)
    {
        if(memo.containsKey(n))
            return memo.get(n);
        if(n<0)
            return null;
        if(n==0)
            return new Vector<Integer>();
        Vector<Integer> bestResult = null;
        for(Integer coin : coin_values)
        {
            Vector<Integer> result = give(n-coin);
            if(result != null)
            {
                result.add(coin);
                if(bestResult == null || bestResult.size() > result.size())
                    bestResult = result;
            }      
        }
        memo.put(n, bestResult);
        return bestResult;
    }
    public static void main(String[] args)
    {
        int n=24;
        memo = new HashMap<>();
        Vector<Integer> result = give(n);
        if(result==null)
            System.out.println("No solution available");
        else
            for(Integer value: result)
                System.out.println(value);
    }
}

它 return 是一个包含 [16, 4, 4, 8] 而期望 [16, 8] 的向量。非常感谢任何帮助！

编辑 25/07：现在它完美运行了！ wallet.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class InfiniteWallet {
    private Map<Integer, ArrayList<Integer>> memo;
    private ArrayList<Integer> coinValues = new ArrayList<Integer>();

    public void addCoin(int coin) {
        coinValues.add(coin);
    }

    public ArrayList<Integer> giveChange(int change) {
        memo = new HashMap<Integer, ArrayList<Integer>>();
        Collections.sort(coinValues);
        Collections.reverse(coinValues);
        return give(change);
    }

    private ArrayList<Integer> give(int n) {
        if (memo.containsKey(n))
            if (memo.get(n) != null)
                return new ArrayList<Integer>(memo.get(n));
            else
                return null;
        if (n < 0)
            return null;
        if (n == 0)
            return new ArrayList<Integer>();
        ArrayList<Integer> bestResult = null;
        for (Integer coin : coinValues) {
            ArrayList<Integer> result = give(n - coin);
            if (result != null) {
                result.add(coin);
                if (bestResult == null || bestResult.size() > result.size())
                    bestResult = result;
            }
        }
        memo.put(n, bestResult);
        if (bestResult != null)
            return new ArrayList<Integer>(bestResult);
        return null;
    }
    
    ArrayList<Integer> getCoinValues(){
        return new ArrayList<Integer>(coinValues);
    }
}

main.java

import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        InfiniteWallet wallet = new InfiniteWallet();
        wallet.addCoin(5);
        wallet.addCoin(395);
        wallet.addCoin(146);
        List<Integer> result = wallet.giveChange(768);
        if (result == null)
            System.out.println("No solution available");
        else
            for (Integer coin : wallet.getCoinValues())
                System.out.println(coin + " " + Collections.frequency(result, coin));
        System.out.println();
    }
}

Answer 1

当您从 memo 检索结果时，如果您想对缓存的矢量进行更改，则需要 return 一个副本。例如，当您执行以下操作时：

result.add(coin)

如果向量 result 是从 memo 中检索到的，那么您将向该原始向量添加 coin（因此也会更改 memo）。

您可以通过简单地（我应该说是一种修复方法）return在 memo 中复制矢量而不是原始矢量来解决此问题。只需替换：

if(memo.containsKey(n))
    return memo.get(n);

和

if(memo.containsKey(n))
    return new Vector(memo.get(n));

这不是最有效的修复方法，但很容易修复。

代币兑换实施问题 (Java)

Issue in coin change implementation (Java)

java

dynamic