Question

PLEASE I HAVE TO RETURN IN 20 MINUTES, I HAVE ALREADY DO THE QUESTION 1, 2, 3, 4 BUT THE QUESTION 5 I CAN'T

In python :

1)Write a sum function expecting an array of integers and returning its sum.

2) Write a multiply function excepting two arrays of integers and returning the product array term by term.

For example mutliply([1,2,3], [5,4,3]) will give [5,8,9]

3) Write a nb1 function expecting an array containing only 0 and 1 and returning the number of 1 present in the array.

4)Write a conFilter function expecting an integer n and creating an array of size n randomly filled with 0 and 1.

5) With these functions offer a random solution to the backpack problem. Here are some indications:

- The consFilter function allows you to construct an array retaining only one part of the objects to place in your backpack. So if the list of objects is [1,4,6,1] and the filter is [1,0,1,0], then by doing the product of the two you will get [1,0,6,0].

- You can generate a large number of random filters, for each of these filters to test if the objects thus filtered fit in the backpack. The rest comes down to a maximum calculation.

- You must make the best list of the weights of the objects fitting in the backpack. For example, if your backpack can hold 20kg, the list of items is [10, 1, 5, 8, 3, 9], one of the ways to optimize your bag is to put [10, 1, 3, 5] or 19kg.

Test on tables of 10-15 objects between 1 and 100kg each for a bag weight of 200 to 300kg.

Answer 1

There are two functions for part 5 in the code below. Modify no. of iterations for more optimised answer for second function.

from random import randint
def sum(L):
    s = 0
    for x in L:
        s += x
    return s

def multiply(L, F):
    C = [L[i] * F[i] for i in range(len(L)) ]
    return C

def nb1(A):
    count = 0
    for x in A:
        if x == 1:
            count += 1
    return count

# uses all possible filters
def consFilter(L, maxCapacity):
    n = len(L)
    maxSum = 0
    optimumSequence = None
    # generate all filters
    for i in range(pow(2, n)):
        # convert i to binary and fill with zeroes
        binary_string = f'{i:b}'.zfill(n)
        F = [int(x) for x in binary_string]
        
        P = multiply(L, F)
        Sum = sum(P)
        
        if Sum <= maxCapacity and Sum > maxSum:
            maxSum = Sum
            optimumSequence = P
    return maxSum, optimumSequence

# generates N filter randomly
def consFilterRandom(L, maxCapacity, N):
    n = len(L)
    maxSum = 0
    optimumSequence = None
    for i in range(N):
        # list of n random integers bw 0 and 1
        F = [ randint(0, 1) for i in range(n) ]
        P = multiply(L, F)
        Sum = sum(P)
        
        if Sum <= maxCapacity and Sum > maxSum:
            maxSum = Sum
            optimumSequence = P
    return maxSum, optimumSequence

maxCapacity = int(input())
objects = [int(x) for x in input().split()]

print(consFilter(objects, maxCapacity))

iterations = 100
print(consFilterRandom(objects, maxCapacity, iterations))

Screenshots: