How can I find whether my output fits the criteria or not?-CodePudding

Write a function processOrders(orders:List[int], sizes:List[int]) to determine whether or not each of the given orders can be fulfilled. Here, orders is a list of positive integers, where each integer represents the length as requested by that order. sizes is a list of positive integers (not necessarily ordered from small to large) representing the individual rod lengths that this store carries. Your function must return a list of booleans, where the i-th element indicates whether or not the i-th order can be fulfilled.

processOrders([5, 12, 13, 20], [1, 2, 5, 10]) == [True, True, True, True]

In the above example, the store carries rods of lengths: 1, 2, 5, 10. The order of 5-cm can be fulfilled because the store sells 5-cm rods. Also, the order of 12-cm can be fulfilled because the store combines 2-cm and 10-cm rods. The order of 13-cm can be fulfilled because it's 10 2 1. The order of 20-cm can be fulfilled because the store welds together two 10-cm rods.

I have tried to do this but it doesn't work..

def findsum(s,g): 
       for f in g:         
           for x in s:            
               if sum (x) == f:               
                  return True            
               else:                         
                  return False

what changes do I need to make?

Edit: any combination should work :)

CodePudding user response：

How about this.

import itertools

def processOrders(orders, sizes):
    """
    Ref:
      https://docs.python.org/3/library/itertools.html#itertools.combinations
      https://stackoverflow.com/questions/70331554/how-can-i-find-whether-my-output-fits-the-criteria-or-not#70331554
    """
    ret = []
    omax = max(orders)  # generate combo for up to max of orders
    
    # combine all sizes and get the sum and save to list
    all_sizes = []
    for i in range(1, omax   1):
        all = itertools.combinations_with_replacement(sizes, i)
        for j in list(all):
            sj = sum(j)
            all_sizes.append(sj)            
    all_sizes = list(set(all_sizes))  # remove duplicates  
    # print(f'all sizes: {all_sizes}')
    
    # Read each value in the orders and check it in all_sizes.    
    for o in orders:
        if o in all_sizes:
            ret.append(True)
        else:
            ret.append(False)
            
    return ret
                
       
# Start
res = processOrders([5, 12, 13, 2], [1, 2, 5, 10])
print(res)  # [True, True, True, True]

res = processOrders([5, 12, 13, 100, 45], [4, 8, 12, 16])
print(res)  # [False, True, False, True, False]

CodePudding user response：

This problem is very similar to a problem that represents dynamic programming, called the coin change problem. In this problem, we just try to verify that there is a possible combination to achieve a sum, while in the coin change problem we check to see how many possible combinations exist.

I'll first post the code for this problem, then explain the implementation to the coin change problem, and then explain how we can just tweak it a bit to fit this problem.

Code:

def findWays(order, sizes):
    ways = [0] * (order   1);
    ways[0] = 1;
    for i in range(len(sizes)):
        for j in range(len(ways)):
            if (sizes[i] <= j):
                ways[j]  = ways[(j - sizes[i])];
        if ways[len(sizes) - 1] > 0:
          return True;
    return False
 
def processOrders(orders,sizes):
    fulfilled = [False] * len(orders)
    for i in range(len(orders)):
      fulfilled[i] = findWays(orders[i],sizes)
    
    for i in range(len(fulfilled)):
      print(fulfilled[i])

processOrders([5, 12, 13, 20], [1, 2, 5, 10])
#Output: True True True True

The key to this problem is understanding how to break it up into smaller problems. First, let us assume that the sizes list is sorted.

Let's start with a small example:

We want a sum of value 5 with 1, 2, and 3 valued coins.

Now, let's create an array that lists out how many ways we can make sums of values from 0 to 5. We set the 0th index to 1 because there is only one way to make a sum of 0. I'll list them with indexes and values:

[0, 1, 2, 3, 4, 5]

[1, 0, 0, 0, 0, 0]

Now, let's start with our value-1 coin. Starting with index 1, since that's the value of the coin, let's add 1 to that value because by just using a value 1 coin, we have 1 way to make 1:

[0, 1, 2, 3, 4, 5]

[1, 1, 0, 0, 0, 0]

However, if we have 1 way to make 1, then by adding 1, we can make 2. Therefore, if we have 1 way to make 2, by adding 1, we can make 3. We can repeat this process until we reach 5:

[0, 1, 2, 3, 4, 5]

[1, 1, 1, 1, 1, 1]

Now, let's start with our value-2 coins. We start at index 2. Using the same process, we increase the value of 2 by 1:

[0, 1, 2, 3, 4, 5]

[1, 1, 2, 1, 1, 1]

Now, with a similar style of thinking: If there is already 1 way to make the value of 1, then by adding a value-2 coin, we have a new way to get 3. If there are already 2 ways to get the value of 2, then by adding value-2 coins, we have 2 new ways to get 4. If there are already 2 ways to get the value of 3, then by adding value-2 coins, we have 2 new ways to get 5:

[0, 1, 2, 3, 4, 5]

[1, 1, 2, 2, 3, 3]

Now, with the value-3 coins: Increase the value of 3 by 1. If there is 1 way to get 1, then by adding a value-3 coin, we have 1 new way to get 4. If there are already 2 ways to get 2, by adding value-3 coins, we have 2 new ways to get 5:

[0, 1, 2, 3, 4, 5]

[1, 1, 2, 3, 4, 5]

We have gone through all of our coins, and we can thus conclude that there are 5 ways to get the value of 5 with coins valued 1, 2, 3. Let's verify our results manually:

5 ways to get a sum of 5:

1 1 1 1 1

1 2 2

2 3

1 1 3

1 1 1 2

For the implementation of this problem, every time we check a valued coin (or size in this case), we will check if the value at index order of the number of ways it can be made is 1 or more. If it is, we will exit the loop and return true.

This was a really long explanation so let me know if you need anymore help!