找出与使用每个数字相关的成本的最大值 [英] finding out the maximum number if cost is associated with using each digit

问题描述

我已经得到了我所拥有的全部钱。现在我知道写下每个数字（1到9）所花费的成本。那么如何从中创建最大数量呢？有没有针对此问题的动态编程方法？

I have been given the total money I have. Now I know the cost it takes to write down each digit (1 to 9). So how to create a maximum number out of it? Is there any dynamic programming approach for this problem?

示例：

可用总资金= 2

每个数字的成本（1到9）= 9、11、1、12、5、8、9、10、6

输出：33

total money available = 2
cost of each digit (1 to 9) = 9, 11, 1, 12, 5, 8, 9, 10, 6
output:33

推荐答案

这是在 Bernhard Baker的答案 。
这个问题是由Providence Health Services在我的hackerank考试中提出的。

Here is the code implemented on the algorithm proposed by Bernhard Baker's answer. The question was asked in my hackerank exam conducted by Providence Health Services.

    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()

这篇关于找出与使用每个数字相关的成本的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！