I have this question: you have a list of [7,9,11] pens. you have a function:

def can_i_buy(x):

you need to check whether or not if you can buy the exact amount.
for example, I have X=23
I can buy 1*9, 2*7
I just need to return True if it is able, false else.
I saw the answer, they did it brute force with 3 for loops ( crazy ).
I tried recursion, it is good, but seems like it is long duplicated parts its not exactly good, cus I don't know where to put the False statement.. what is my exit point.
The code works, but not exactly.

def can_i_buy(x):  # 23
return helper(x, [7,9,11])
def helper(x, lst):
    if x == 0:
        return True
    if x < 0:    
        return
    take_1 = helper(x - lst[0], lst)
    if take_1 == True:
         return take_1
    take_2 = helper(x - lst[1], lst)
    if take_2 == True:
        return take_2
    take_3 = helper(x - lst[2], lst)
    if take_3 == True:
        return take_3

How to fix it? also, what is my thought on the exit statement here? I dont know how to exit it... Where should I put false, and how?

Edit: added prints outputs

print(can_i_buy(24))
print(can_i_buy(23))
print(can_i_buy(7))
print(can_i_buy(14))

output:

None
True
True
True

I should receive at none - False. but I dont know where to put the False statement... when all the recursion end, I dont know how to put it.

CodePudding user response：

The recursive call should be made with each price subtracted from x, until x is either 0 (in which case return True) or less than 0 (in which case return False):

def can_i_buy(x, lst):
    return not x or x > 0 and any(can_i_buy(x - i, lst) for i in lst)

If you just want your code fixed, you can return False at the end of the function when all conditions that would return True fall through:

def helper(x, lst):
    if x == 0:
        return True
    if x > 0:    
        take_1 = helper(x - lst[0], lst)
        if take_1 == True:
             return take_1
        take_2 = helper(x - lst[1], lst)
        if take_2 == True:
            return take_2
        take_3 = helper(x - lst[2], lst)
        if take_3 == True:
            return take_3
    return False

Or if you are allowed to make a for loop:

def helper(x, lst):
    if x == 0:
        return True
    if x > 0:
        for i in lst:
            if helper(x - i, lst):
                return True
    return False

Demo: https://replit.com/@blhsing/MortifiedImmediateCheckpoint

CodePudding user response：

I used this technique which combined breadth-first search and dynamic programming to solve these kinds of problems. You can change it depending on your use cases(for example if we need to return how we create the value).

def can_i_buy(target_value, values):
    possible_values = {0: True}
    values_to_be_handled = [0]

    while values_to_be_handled:
        value = values_to_be_handled.pop(0)
        if value == target_value:
            return True
        for val in values:
            next_value = value   val
            if next_value > target_value:
                continue
            if next_value not in possible_values:
                possible_values[next_value] = True
                values_to_be_handled.append(next_value)

    return None

CodePudding user response：

This is classical dynamic-programming question, you can solve it via recursion:

def can_i_buy(alist, target):
    if target == 0:
        return True
    if target < 0:
        return False

    for i in range(len(alist)):
        if can_i_buy(alist, target - alist[i]):
            return True

    return False

print(can_i_buy([7, 9, 11], 18))

CodePudding user response：

I just need to return True if it is able, false else.

The way we handle this using dynamic programming, properly, is:

• Initialize an array (list, in Python) of booleans N to false (except for a true value at 0, since of course we can spend $0 exactly), where the meaning is that N[i] tells us whether we can buy pens with i dollars.

• Iterate forwards through the array: if we find a false value while iterating, then the answer is false for that i value. Otherwise, it is true for that i value and we update further positions in the array, to indicate that we found a solution for those i values as well. (That is: once we know we can buy pens with $11 exactly, we also know that we can buy pens with $11 7, $11 9, and $11 11 exactly, so we fill in those values for when we get to them.

It looks like, for example:

def canibuy(dollars, pen_costs):
    # To find out for example if we can spend $23, we need 24 booleans,
    # representing the results for 0 to 23 *inclusive*.
    results = [True]   [False] * dollars
    for amount in range(len(results)):
        if results[amount]:
            # we can spend this amount exactly, so also update other values.
            for pen_cost in pen_costs:
                if (amount   pen_cost) < len(results):
                    results[amount   pen_cost] = True
    return results[-1]

CodePudding user response：

Where should I put false, and how?

Everywhere that False should be returned. For example:

    if x < 0:    
        return

The underlying logic is: "if the amount of money to be spent is less than $0, then we know that we cannot do it". So - the result should be False, the value that indicates that we cannot do it. So we should write return False instead.

We should also return False at the end of the function, because if we get there, it means that we did not find a way to spend the money by our recursive algorithm. If we can't spend the remainder of the money after buying any of the possible pens, then we know that we cannot spend the money, and thus False is the correct return value.