给定 N 个硬币，每个硬币最多可以使用 T 次。是否有可能使用最少的 N 个硬币来创造价值 W？

Question

输入格式：

N T（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;
}

Answer 1

代码问题：

你检查 if(us[p]<T) 但是当调用函数时你减去 w-coins[p]...

根据您的逻辑，此块：

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 和不同值 [= 的状态时18=]..您的解决方案将不起作用..

解决方案：

你需要用硬币数组取新数组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;
}

给定 N 个硬币，每个硬币最多可以使用 T 次。是否有可能使用最少的 N 个硬币来创造价值 W？

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

c

algorithm

dynamic-programming

coin-change

代码问题：

你的解决问题：

解决方案：