algorithm - 如果成本与使用每个数字相关，则找出最大数量

Question

我已经得到了我所有的钱。现在我知道写下每个数字（1 到 9）所需的成本。那么如何创建一个最大数量呢？这个问题有什么动态规划方法吗？

例子：

可用总资金 =
每个数字的 2 成本（1 到 9）=9, 11, 1, 12, 5, 8, 9, 10, 6
输出：33

Answer 1

这是在Bernhard Baker 的回答提出的算法上实现的代码。这个问题是在我由普罗维登斯健康服务组织进行的hackerank 考试中提出的。这个问题在采访中通常被问为最大数量的疫苗。

    total_money = 2   
    
    cost_of_digit = [9, 11, 1, 12, 5, 8, 9, 10, 6]
    
    # Appending the list digits with [weight, number] 
    k=1
    digits=list()
    
    for i in cost_of_digit:
        digits.append([i,k])
        k+=1
    
    #  Discarding any digits that cost more than a bigger digit: (because it's never a good idea to pick that one instead of a cheaper digit with a bigger value)
    i = 8
    while(i>0):
        if digits[i][0] <= digits[i-1][0]:
            del digits[i-1]
            i-=1
        else:
            i-=1
    
    # Sorting the digits based on weight
    digits.sort(key=lambda x:x[0],reverse=True)
    
    max_digits = total_money//digits[-1][0] # Max digits that we can have in ANSWER
    selected_digit_weight = digits[-1][0] 
    
    ans=list()
    
    if max_digits > 0:
        for i in range(max_digits):
            ans.append(digits[-1][1])
    
    # Calculating extra money we have after the selected digits
    extra_money = total_money % digits[-1][0]
    
    index = 0
    
    # Sorting digits in Descending order according to their value
    digits.sort(key=lambda x:x[1],reverse=True)
    
    while(extra_money >= 0 and index < max_digits):
        temp = extra_money + selected_digit_weight # The money we have to replace the digit
        swap = False # If no digit is changed we can break the while loop 
        
        for i in digits:
            # Checking if the weight is less than money we have AND the digit is greater than previous digit
            if i[0] <= temp and i[1] > digits[-1][1]: 
                ans[index] = i[1]
                index += 1
                extra_money = temp - i[0]
                swap = True
                break
        if(not swap):
            break
    
    if len(ans) == 0:
        print("Number cannot be formed")
    else:
        for i in ans:
            print(i,end="")
        print()

Answer 2

我认为您不需要动态编程，只需执行以下操作：

• 尽可能多地选择成本最低的数字。
• 现在您有一个数字（仅由一种数字组成）。
• 用您能承受的最大可能数字替换第一个数字
• 如果你还有钱，第二个、第三个也一样，以此类推，直到你的钱用完。

为什么这样有效：

考虑11111>9999和91111> 88888，或者，换句话说，最好：

• 选择尽可能多的数字，这是通过选择最便宜的数字来完成的。
• 然后从左边用你能负担得起的最高值替换这些数字（这总是比选择几个更昂贵的数字开始要好）。

优化：

为了有效地做到这一点，请丢弃任何花费超过更大数字的数字：（因为选择那个而不是更便宜的具有更大价值的数字从来都不是一个好主意）

Given:
9, 11, 1, 12, 5, 8, 9, 10, 6
Removing all those where I put an X:
X, X, 1, X, 5, X, X, X, 6
So:
1, 5, 6

现在您可以对其进行二进制搜索（只需记住哪个数字来自哪个值）（尽管只有 9 位数字，二进制搜索并不能真正为已经很小的运行时间创造奇迹）。

运行时间：

O(n)（有或没有优化，因为 9 是常数）

Answer 3

解决背包问题

和

• 成本 = 数字成本
• 值 = 数字（9 优于 1）

然后按递减排序。