узнать максимальное число, если стоимость связана с использованием каждой цифры

Вот код, реализованный на основе алгоритма, предложенного ответом Бернхарда Бейкера. Этот вопрос был задан на моем экзамене по хакерскому званию, проведенном 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()

Я не думаю, что вам нужно динамическое программирование, просто сделайте следующее:

• Выберите столько цифр, которые стоят меньше всего, сколько вы можете себе позволить.
• Теперь у вас есть число (состоит только из 1 типа цифр).
• Замените первую цифру максимально возможной цифрой, которую вы можете себе позволить.
• Если у вас остались деньги, сделайте то же самое для второго, третьего и так далее, пока не закончатся деньги.

Почему это работает:

Учтите, что 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 — константа)

Решить проблему с рюкзаком

с

• Стоимость = Стоимость цифры
• Значение = цифра (9 лучше, чем 1)

затем отсортировать по убыванию.