Maximum sum combinations from 4 arrays-CodePudding

I have 4 arrays with 2 colomns : one column measuring meters and the other measuring the money you get per meter, I want to get the highest sum combinations from these 4 arrays but I have 2 rules : the first rule is that each meter value in the sum has to be between 1 and 6 meters, and the second rule is that the meter value of the result has to be equal to 12 meters. I have written a code that gets the maximum sum out of a series of 4 arrays but I don't know how to implement the 2 rules in the code. This is why i am asking for your help.

My 4 arrays :

1,2,3,4,5,6 are the meter values and the numbers below the meter values is the money earned by meters

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]]

My code :


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)

CodePudding user response：

As it has been said in the comments other approaches may be more efficient. And of course we need to put the meters data in the list together with the prices:

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

Then, if we want to keep your approach (just allow me to use itertools.product instead of those 4 for loops) a possible solution would be:

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

CodePudding user response：

This can be solved with additional info that wasn't in the question. The meter number is just the one-based index of the array. (see comments, and OP: please edit that info into the question. External links to pictures aren't allowed.)

Since you're not familiar with dynamic programming, and this problem suits itself to a brute force approach, we'll do that. You just need the meter number to check the constraints, which you can get from python's enumerate.
https://docs.python.org/3/library/functions.html#enumerate

Your for loops over a container should not be based on an index, but rather something simple like "for a in A", but since we want the index as well, let's do this

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)

We can check the constraints first, and only include the values that pass in the priority queue.

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

When you do this kind of brute forcing, you really want to use itertools. What you've done with these for loops is basically itertools.product.
https://docs.python.org/3/library/itertools.html#itertools.product

Additionally, itertools doesn't care how many different sets of meters you have. It would be easy (with some practice) to write a function like KMaxCombinations(collection_of_meters, target=12, K=3) using itertools.

Additionally, you can chain iterators like enumerate directly into the product. You can also use itertools.islice to skip candidates that can't meet the criteria. That doesn't help in this particular problem, but if the 12 were different, it might be high enough that you can entirely skip the first few readings. Or if it's low enough, you can skip the last several readings.

CodePudding user response：

Here's a modification of posted code to solve for solution.

Using exhaustive search as posted code

Changes:

Used heapq as PriorityQueue
Made A, B, C, D 2-dimensional lists to add meters
Added if conditionals to implement rules

Code

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

Test

# 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")

Output

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