Максимальное количество монет, необходимое для внесения изменений

Question

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

Пример Скажем, мне даны монеты со значениями 3 и 5, и я хочу внести изменение для 15, решение будет {3,3,3,3,3} (спасибо JoSSte за указание) Аналогично, скажем, учитывая монеты достоинством 3 и 5, и я хочу внести изменение для 7, мне нужно отобразить "Решение не возможно"

Я смог сделать это для поиска минимального количества монет следующим образом

import java.util.ArrayList;
import java.util.Arrays;


public class Minimum
{
    static int[] options = {5,3};

    public static void main(String[] args)
    {
        ArrayList<Integer> result = new ArrayList<Integer>();

        result = fun(15);
        if(result.size() == 999)
             System.out.println("Not possible to make change with this denomination");
        else 
        {
            for(int i = 0;i<result.size();i++)
                System.out.print(result.get(i));
        }
    }

    static ArrayList<Integer> fun(int n)
    {       
        if(n == 0)
        {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }
}

Обратите внимание, что у меня есть проверка, называемая if(n<0), где комбинации, которые не составляют сумму, удаляются из опций, устанавливая их размер очень большим числом, которое не может быть минимальным.

Тем не менее, как я могу изменить выше, чтобы найти максимальное количество монет

Answer 1

Для вашего решения вы должны проверить условие для n=1,2. если n = 1,2, вы можете вернуть ans как 999.

Ваша функция должна быть следующей

 static ArrayList<Integer> fun(int n)
   {       
     if(n == 0)
     {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0 || n==1 || n==2)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }

Надеюсь, это должно работать..

Answer 2

Вот монета изменить код дп в C++.

int coin[] = {3, 5}; //initialize array
int make;
int dp[2][100];

int call(int i, int amount)
{
     if(i >= 2) { // All coins have been taken
          if(amount == make) return 1;
          return 0;
     }

     if(dp[i][amount] != -1) return dp[i][amount];
     int ret1 = 0, ret2 = 0;
     // try to take coin i
     if(amount + coin[i] <= make) ret1 = call(i, amount + coin[i]); 

     ret2 = call(i+1, amount); // don't take coin i
     return dp[i][amount] = ret1 | ret2; // is possible or not?
}

int main()
{
    make = 7;
    memset(dp, -1, sizeof(dp));
    if(call(0, 0) == 0) cout << "not possible" << endl;
    else cout << "possible" << endl;

    return 0;
}

Answer 3

      ll dp[10005][10005];
ll maxCoins(ll arr[],ll n,ll sum)
{
    if(sum == 0) // checking if the sum zero if true return 0
        return 0;
    
    if(sum < 0) // if the sum goes below 0 that is not possible return -infinity
        return INT_MIN;
    
    if(n <= 0) // if the number of coins left is less than or equal to zero tha n return -infinity
        return INT_MIN;
    
    if(dp[n][sum] != -1) // checking if the recursion reached this state before
        return dp[n][sum]; // if yes returning that 
    
    return dp[n][sum] = max(1+maxCoins(arr, n, sum-arr[n-1]),maxCoins(arr, n-1, sum)); // recursive call to maximise the current state we have two options weather to include in our answer or not if yes reduce the sum by that value less call the function without including that
       
}

void solve()
{
    clr(dp);
    ll n,sum;
    cin>>n;
    
    ll arr[n];
    
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    
    cin>>sum;
    
    cout<<maxCoins(arr,n,sum)<<endl;
}