Блог

Я столкнулся с проблемой реализации, пытаясь решить эту классическую проблему с помощью DP. Задача состоит в том, чтобы получить набор монет и вернуть их наилучшим способом, дав наименьшее количество монет.

 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 = resu<
            }      
        }
        memo.put(n, bestResult);
        return bestResu<
    }
    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);
    }
}
 

Он возвращает вектор, содержащий [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 = resu<
            }
        }
        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();
    }
}
 

При извлечении результатов memo вам необходимо вернуть копию , если вы хотите внести изменения в кэшированный вектор. Например, когда вы делаете:

 result.add(coin)
 

если вектор result был получен из memo , то вы добавите coin его к исходному вектору (и, следовательно memo , также измените).

Вы можете исправить это, просто (я бы сказал, одним из способов исправить это) вернув копию вектора, memo а не оригинал. Просто замените:

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

с

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

Это не самый эффективный способ исправить это, но это простое решение.