Given N coins, each coin can be used at most T times. Is it possible to make value W using minimum N coins?

Question

Input Format:

N T (N = number of coins, T = number of times)
C1, C2 .... CN
W

From my solution, I am getting this...

Input:
2 4
5 8
37

Output:
5 (Which is valid, because 37 = (8*4)+(5*1))

Input:
2 2
5 10
30

Output:
3 (Here the output should be 4, because I can't use coins more than 2 times).

Where is the error in my solution?

#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;
}

Answer 1

Code Problem:

you check if(us[p]<T) but when call function u subtract w-coins[p]...

According to your logic this block:

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

would be:

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

Your Solution problem:

Your memorization will not work cause u pass p,w and us[] in function but you memorize only p and w.. As you memorize all state of same value p and w and different value of us[].. your solution will not works..

Solution:

You need to take new array with coin array T times...

Lets coin : 5, 10.. and t = 2

Then new array coin array will be: 5 5 10 10

Now if you want to make 30 then try to make 30 using new array:

Try with this code:

#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;
}