4个数组的最大和组合

Question

我有4个数组，有2列：一列测量米，另一列测量你每米得到的钱，我想从这4个数组中得到最高的总和组合，但我有2条规则：第一条规则是总和中的每个米值必须在1到6米之间，第二条规则是，结果的米值必须等于12米。我已经编写了一段代码，从一系列4个数组中获得最大和，但我不知道如何在代码中实现这2条规则。这就是我请求你帮助的原因

我的4个阵列：

1,2,3,4,5,6是仪表值 米值下面的数字是米赚的钱

A = [[1, 2, 3, 4, 5, 6],
     [50.4, 100.8, 201.6, 403.2, 806.4, 1612.8]] 
B = [[1, 2, 3, 4, 5, 6],
     [40.8, 81.6, 163.2, 326.4, 652.8, 1305.6]]
C = [[1, 2, 3, 4, 5, 6],
     [110, 220, 440, 880, 1760, 3520]]
D = [[1, 2, 3, 4, 5, 6],
     [64, 128, 256, 512, 1024, 2048]]

我的代码：

import math
from queue import PriorityQueue
def KMaxCombinations(A, B, C, D, N, K):

    # Max heap.
    pq = PriorityQueue()

    # Insert all the possible
    # combinations in max heap.
    for i in range(0,N):
        for j in range(0,N):
            for k in range(0,N):
                for l in range(0,N):
                    a = A[i] + B[j] + C[k] + D[l]
                    pq.put((-a, a))
   
    # Pop first N elements from
    # max heap and display them.
    count = 0
    while (count < K):
        print(pq.get()[1])
        count = count + 1


# Driver method
A = [50.4, 100.8, 201.6, 403.2, 806.4, 1612.8]
B = [40.8, 81.6, 163.2, 326.4, 652.8, 1305.6]
C = [110, 220, 440, 880, 1760, 3520]
D = [64, 128, 256, 512, 1024, 2048]
N = len(A)
K = 3

# Function call
KMaxCombinations(A, B, C, D, N, K)

Answer 1

这可以用问题中没有的其他信息来解决。仪表编号只是阵列的基于一的索引。（请参见评论和备注：请将该信息编辑到问题中。不允许图片的外部链接。）

因为您不熟悉动态编程，而且这个问题适合于蛮力方法，所以我们将这样做。您只需要仪表号来检查约束，这可以从python的enumerate中获得。
https://docs.python.org/3/library/functions.html#enumerate

容器上的for循环不应该基于索引，而应该是类似“for a in a”这样的简单内容，但是既然我们也需要索引，那么就这样做吧

for a_meter, a_value in enumerate(A, start=1):
    for b_meter, b_value in enumerate(B, start=1):
        for c_meter, c_value in enumerate(C, start=1):
            for d_meter, d_value in enumerate(D, start=1):
                if check_constraints(a_meter, b_meter, c_meter, d_meter):
                    value = sum((a_value, b_value, c_value, d_value))
                    pq.put(-value, value)

我们可以先检查约束，只包括优先级队列中传递的值

def check_constraints(a, b, c, d):
    return sum((a, b, c, d)) == 12

当你进行这种暴力强迫时，你真的想使用itertools。您使用这些for循环所做的基本上是itertools.product。
https://docs.python.org/3/library/itertools.html#itertools.product

此外，itertools并不关心您有多少不同的仪表组。使用itertools编写类似KMaxCombinations（米的集合，目标=12，K=3）的函数是很容易的（通过一些实践）

此外，您可以将诸如enumerate之类的迭代器直接链接到产品中。您还可以使用itertools.islice跳过不符合条件的候选人。这对这个问题没有帮助，但是如果12个不同，它可能足够高，你可以完全跳过前几个读数。或者如果它足够低，你可以跳过最后几个读数

Answer 2

正如评论中所说，其他方法可能更有效。当然，我们需要将仪表数据与价格一起放在列表中：

A = [(1, 50.4), (2, 100.8), (3, 201.6), (4, 403.2), (5, 806.4), (6, 1612.8)]
B = [(1, 40.8), (2, 81.6), (3, 163.2), (4, 326.4), (5, 652.8), (6, 1305.6)]
C = [(1, 110), (2, 220), (3, 440), (4, 880), (5, 1760), (6, 3520)]
D = [(1, 64), (2, 128), (3, 256), (4, 512), (5, 1024), (6, 2048)]

然后，如果我们想保留您的方法（请允许我使用itertools.product而不是这4个for循环），可能的解决方案是：

def KMaxCombinations(A, B, C, D, N, K):
    pq = PriorityQueue()
    for p in product(A, B, C, D):
        meters, prices = list(zip(*p))
        for m in meters:
            if not (0<m<7):
                allgood = False
                break
        else:
            allgood = True
        if allgood and (sum(meters) == 12):
            a = sum(prices)
            pq.put((-a, a))

    count = 0
    while (count < K):
        print(pq.get()[1])
        count = count + 1

KMaxCombinations(A,B,C,D,N,K)
4123.2
4028.0
3960.8

Answer 3

下面是对发布代码的修改，以解决此问题

使用穷举搜索作为发布代码

变化：

• 使用heapq作为优先队列
• 制作A、B、C、D二维列表以添加仪表
• 添加了if条件以实现规则

代码

import heapq

def KMaxCombinations(A, B, C, D, N, K):
    # Trying all combinations of the rows of A, B, C, D
    priority_queue = []
    
    for i in range(0,N):
        if 1 <= A[0][i] <= 6: # the first rule is that each meter value in the sum has to be between 1 and 6 meters
            for j in range(0,N):
                if 1 <= B[0][j] <= 6: # the first rule is that each meter value in the sum has to be between 1 and 6 meters
                    for k in range(0,N):
                        if 1 <= C[0][k] <= 6: # the first rule is that each meter value in the sum has to be between 1 and 6 meters
                            for l in range(0,N):
                                if 1 <= D[0][l] <= 6: # the first rule is that each meter value in the sum has to be between 1 and 6 meters
                                    # second rule is that the meter value of the result has to be equal to 12 meters
                                    if A[0][i]  + B[0][j] +  C[0][k]+ D[0][l] == 12:
                                            money_obtained = A[1][i] + B[1][j] + C[1][k] + D[1][l]
                                        
                                            # Add another solution to priority queue
                                            heapq.heappush(priority_queue, (-money_obtained, i, j, k, l))
                                                
    return heapq.nsmallest(K, priority_queue)[K-1]  # K-th most money
                                                    # use smallest since money is negative 
                                                    # value to make max heap

测试

# Use 2D list for meters and money
# A[0]  - list of meters
# A[1]  - list of money
# same for B, C, D
A = [[1, 2, 3, 4, 5, 6],
     [50.4, 100.8, 201.6, 403.2, 806.4, 1612.8]] 
B = [[1, 2, 3, 4, 5, 6],
     [40.8, 81.6, 163.2, 326.4, 652.8, 1305.6]]
C = [[1, 2, 3, 4, 5, 6],
     [110, 220, 440, 880, 1760, 3520]]
D = [[1, 2, 3, 4, 5, 6],
     [64, 128, 256, 512, 1024, 2048]]

K = 3  # 3rd best solution
solution  = KMaxCombinations(A, B, C, D, len(A[0]), K)

# Show result
if solution:
    max_money,*sol = solution
    print(f'{K}rd Max money is {max_money}')
    print(f'Using A[{sol[0]}] = {A[0][sol[0]]}')
    print(f'Using B[{sol[1]}] = {A[0][sol[1]]}')
    print(f'Using C[{sol[2]}] = {A[0][sol[2]]}')
    print(f'Using D[{sol[3]}] = {A[0][sol[3]]}')
    print(f'Sum A, B, C, d meters is: {A[0][sol[0]]  + B[0][sol[1]] + C[0][sol[2]] + D[0][sol[3]]}')
else:
    print("No Solution")

输出

3rd Max money is 3960.8
Using A[0] = 1
Using B[3] = 4
Using C[5] = 6
Using D[0] = 1
Sum A, B, C, d meters is: 12