两个输入的最佳组合

Question

有人可以用python语言解决这个问题吗？

Answer 1

我认为这是您想要的

注意：X的值大于Y。

def table_arrange(x,y,d):
    list_of_lists = []
    a = d//x
    b = list(x for i in range(0,a))
    while sum_of_list(b)+y <= d:
        b.append(y)
    array = b.copy()
    list_of_lists.append(array)
    list_of_lists =  arrange(list_of_lists,b,x,y,d)
    differnce = y
    optimum = []
    for lists in list_of_lists:
        a  = d - sum_of_list(lists)
        if differnce > a:
            optimum = lists
            differnce = a 
    f = optimum.count(x)
    g = optimum.count(y)
    return [f,g,differnce]

def arrange(list_of_lists,b,x,y,d):
    c = []
    for i in range(b.count(x)):
        b.pop(0)
        while sum_of_list(b)+y <= d:
            b.append(y)
            c = b.copy()
        list_of_lists.append(c)
    return list_of_lists

def sum_of_list(list_):
    a = 0
    for i in list_:
        a = a+i
    return a

print(table_arrange(5,3,21))

Answer 2

您可以使用DP来解决它。这是一个学习DP的好网站：https://www.geeksforgeeks.org/dynamic-programming/

# For example X=3, Y=5, D=24. If we know solution for D=21 (24-3) and D=19 (24-5), then we know for D=24 the solution is min(D=21, D=19) +1.
# And for D=19, we know it's min(D=16, D=14) +1. So all the way back to D=3 and D=5.
def sol(X,Y,D):

    # dp list for storing the solution for each D.
    # For inner list, index 0 represent the usage of X, index 1 represent the usage of Y.
    dp = [[float('inf'), float('inf')] for _ in range(D+1)]

    # Assume X <= D and Y <= D, it guarantees both X and Y can fit in D.
    # for D=X, the solution is 1X, 0Y, so it's[1,0]
    dp[X] = [1,0]
    # for D=Y, the solution is 0X, 1Y, so it's[0,1]
    dp[Y] = [0,1]

    for i in range(min(X,Y)+1, D+1):

        # If already has a solution, skip. 
        if dp[i][0] != float('inf'):
            continue

        # Current D= min(D-X, D-Y) + 1
        if sum(dp[i-X]) < sum(dp[i-Y]):
            dp[i][0] = dp[i-X][0]+1
            dp[i][1] = dp[i-X][1]
        else:
            dp[i][0] = dp[i-Y][0]
            dp[i][1] = dp[i-Y][1]+1

    # Search for a solution backward.
    for i in range(len(dp)-1, -1, -1):
        if dp[i][0] != float('inf') and dp[i][1] != float('inf'):
            return (D-i, dp[i][0], dp[i][1])
    return (D-i, 0, 0)

print(sol(3,5,24))