仅使用超过阈值的指定面额的硬币可以获得的最小金额-Java 学习之路

换句话说，给定一组n个正整数 A 和一个阈值 B ，我想找到最小的 C ，这样：

C > B
C = A[1] * k[1] + A[2] * k[2] + ... + A[n] * k[n] ， k[i] 是整数> = 0

作为示例 A = { 6, 11, 16 } 然后我们可以获得的值是： { 0, 6, 11, 12, 16, 17, 18, 22, 23, 24, 27, 28, 29, 30, 32 ... } 所以如果 B = 14 那么 C 将是 16 ， B = 22 => C = 23 ， B = 18 => C = 22

这个问题得到了这些限制： 2 < n < 5000 0 < A[i] < 50000 和 1 < B < 10^9 （这就是我被困的原因） . 此外，你必须计算一个数组 B 大小 < 1000 数组C（但这可能无关紧要） . 并且算法应该在C中以0.3秒的速度运行 .

像这里描述的那样的算法解决了它，但它不够快：https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
我计算表直到B Amin因为 Amin * k <= B <= Amin * ( k + 1 ) <= B + Amin
这是算法（在伪C中）：

int n, A[n], B;
int Amin; // smallest number from A

// table[i] will tell us if it is possible or not to obtain the number i
bool table[B + Amin];
table[0] = true;
for( int i = 0; i < n; ++i )
{
    int x = A[i]; // current number / denomination
    for( int j = x; j <= B + Amin; ++j )
        if( table[j - x] ) 
            table[j] = true;
}

// now we can do something like this:
int result = B + 1;
while( !table[result] ) 
    ++result;

这个算法的复杂性为 O(n*B) ，我正在寻找一些独立于 B （或者可能有 O(log(B)) 或 O(sqrt(B)) ）的东西

注意：如果我们提出第一个要求 C >= B 那么问题不会改变（只需将B加1）我们可以这样问：如果我们有特定的硬币或纸币（无限的）并想要用它们购买东西那么我们可以支付的金额是多少，这样收银员就必须给予最小的改变 .

我怀疑的事情可能会有所帮助：
https://en.wikipedia.org/wiki/Coin_problem
如果最大公约数 ( x, y ) = 1 ，则可以使用 x 和 y 获得高于 xy − x − y 的任何值 .

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

https://en.wikipedia.org/wiki/Subset_sum_problem

编辑：添加示例和注释 .

1 回答

1
我不认为你可以比O（n * B）更好，因为49999和49998的Frobenius数字（高于这个数字所有金额都可以使用给定的面额建造）是2499750005比10 ^ 9大很多你和你需要至少为某些输入计算最佳值 . 如果gcd（A）> 1那么Frobenius数不存在，但可以通过将所有A和B（向下舍入）除以gcd（A）并将你得到的C乘以gcd（A）来得到最后结果 .

您的伪代码仍有很大的改进空间 . 您可以查看所有面值几乎为B Amin的时间，并将表中的值设置为true多次 .

标准实现看起来像这样：
```
sort(A);
table[0] = true;
for (int i = A[0]; i <= B + A[0]; i++)
    for (int j = 0; j < n && A[j] <= i; j++)
        if (table[i - A[j]]) {
            table[i] = true;
            break;
        }
```
这已经好一点了（注意休息） . 我把它称为向后实现，因为你回顾表中的所有位置，看看你是否能找到一个与给定面额之一有差异的值 . 您还可以为表中设置为true的连续值的数量引入计数器（当您将表中的值设置为true时增加计数器，如果无法构建值则重置计数器，如果计数器==则返回B 1 A [0] - 1） .

也许你甚至可以通过正向实现获得更好的结果，因为表格可能非常稀疏，这里的表值是false而不是面额：
```
table[0] = true;
for (int i = 0; i <= B + Amin; i++)
    if (table[i])
        for (j = 0; j < n; j++)
            if (i + A[j] <= B + Amin)
                table[i + A[j]] = true;
```
回复于 2024-04-28T15:44:07+08:00

仅使用超过阈值的指定面额的硬币可以获得的最小金额

1 回答

相关问题