Учитывая N монет, каждая монета может использоваться не более T раз. Можно ли сделать значение W, используя минимум N монет? - PullRequest
Новая
       82

Учитывая N монет, каждая монета может использоваться не более T раз. Можно ли сделать значение W, используя минимум N монет?

3 голосов
/ 01 мая 2020

Формат ввода:

NT (N = количество монет, T = количество раз)
C1, C2 .... CN
W

Из моего решения я получаю это ...

Ввод:
2 4
5 8
37

Выход:
5 (Это действительно, потому что 37 = (8 * 4) + (5 * 1))

Ввод:
2 2
5 10
30

Вывод:
3 (Здесь вывод должен быть 4 , потому что я не могу использовать монеты более чем в 2 раза).

Где ошибка в моем решении? 

#include<bits/stdc++.h>
using namespace std;
int coins[100], N, T, mem[100][100];
int solve(int p, int w, int us[])
{
    if(p==N || w<=0){
        if(w==0) return 0;
        return 1e5;
    }
    if(mem[w][p]!=-1) return mem[w][p];
    int ans=1e5;

    if(us[p]<T){
        us[p]++;
        ans=min(1+solve(p, w-coins[p], us), ans);
        us[p]--;
    }
    ans=min(ans, solve(p+1, w, us));
    return mem[w][p]=ans;
}
int main()
{
    cin>>N>>T;
    for(int i=0;i<N;i++){
        cin>>coins[i];
    }
    int w, us[100];
    cin>>w;
    memset(mem, -1, sizeof (mem));
    memset(us, 0, sizeof (us));
    cout<<solve(0, w, us)<<endl;
    return 0;
}

1 Ответ

1 голос
/ 01 мая 2020

Проблема с кодом:

Вы проверяете if(us[p]<T), но при вызове функции u вычитаете w-coins[p] ...

Согласно вашей логике c этот блок: 

if(us[p]<T){
        us[p]++;
        ans=min(1+solve(p, w-coins[p], us), ans);
        us[p]--;
    }

будет: 

if(us[coins[p]]<T){
        us[coins[p]]++;
        ans=min(1+solve(p, w-coins[p], us), ans);
        us[coins[p]]--;
    }

Ваша проблема Решения:

Ваше запоминание не будет работать, потому что вы передаете p,w and us[] в функции, но вы запоминаете только p and w .. Как вы запомнить все состояния с одним и тем же значением p and w и с другим значением us[] .. ваше решение не будет работать ..

Решение:

Вам нужно взять новый массив с массивом монет T раз ...

Позволяет монете: 5, 10 .. и t = 2

Тогда новый массив монет будет: 5 5 10 10

Теперь, если вы хотите сделать 30, затем попробуйте сделать 30, используя новый массив:

Попробуйте с этим кодом: 

#include <bits/stdc++.h>

using namespace std;
int coins[5005], N, M, T, mem[105][5005];
int solve(int p, int w)
{
    if(p==N || w<=0){
        if(w==0) return 0;
        return 1e5;
    }
    if(mem[w][p]!=-1)
        return mem[w][p];
    return mem[w][p] = min(solve(p+1,w), 1 + solve(p+1, w-coins[p]));
}
int main()
{
    cin>>N>>T;
    M = 0;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        for (int j = 0; j < T; j++) {
            coins[M++] = a;
        }
    }
    N = M;
    int w, us[100];
    cin>>w;
    memset(mem, -1, sizeof (mem));
    cout<<solve(0, w)<<endl;
    return 0;
}
...