Почему мой подход динамического программирования к SSP всегда работает?

Question

Почему мой код работает в 100% случаев? Я хочу создать 100 случайных выборок вывода этого кода для измерения скорости, но каждый раз, когда я запускаю, я получаю 100 истинных результатов и 0 ложных результатов. Может ли кто-нибудь предложить мне совет?

import random 
from random import randint, sample 
from itertools import chain, combinations 
import time 

class SSP(): 
    def __init__(self, S=[], t=0): 
     self.S = S 
     self.t = t 
     self.n = len(S) 
     # 
     self.decision = False 
     self.total = 0 
     self.selected = [] 

    def __repr__(self): 
     return "SSP instance: S="+str(self.S)+"\tt="+str(self.t) 

    def random_instance(self, n, bitlength=10): 
     max_n_bit_number = 2**bitlength-1 
     self.S = sorted([randint(0,max_n_bit_number) for i in range(n)], reverse=True) 
     self.t = randint(0,n*max_n_bit_number) 
     self.n = len(self.S) 

    def random_yes_instance(self, n, bitlength=10): 
     max_n_bit_number = 2**bitlength-1 
     self.S = sorted([randint(0,max_n_bit_number) for i in range(n)], reverse=True) 
     self.t = sum(sample(self.S, randint(0,n))) 
     self.n = len(self.S) 

    def try_at_random(self, S, n, t): 
     #if sum is 0, use empty set as our solution 
     if (t == 0): 
      return True 
      print("Found a subset with given sum") 
     #if n is 0 and sum is not 0, no solution possible 
     if (n == 0 and t != 0): 
      return False 
      print("No subset within given sum") 

     if (S[n-1] > sum): 
      return instance.try_at_random(S, n-1, t) 
     else: 
      return instance.try_at_random(S, n-1, t) or instance.try_at_random(S, n-1, t-S[n-1]) 

i=0 
tr = 0 
fa = 0 
instance = SSP() 

for i in range (0, 100): 
    instance.random_yes_instance(4) 
    print(instance) 

    start_time = time.time() 

    if (instance.try_at_random(instance.S, instance.n, instance.t) == True): 
     print("Found a subset with given sum") 
     tr += 1 
    else: 
     print("No subset within given sum") 
     fa += 1 

    time_after = time.time() - start_time 
    print ("Time taken: " +str(time_after)+"s") 
    i+=1 
print ("Times succeeded: ", tr) 
print ("Times failed: ", fa) 

Heres выход образца:

SSP instance: S=[754, 429, 232, 131] t=131 
Found a subset with given sum 
Time taken: 0.0s 
SSP instance: S=[954, 903, 768, 184] t=0 
Found a subset with given sum 
Time taken: 0.0s 
SSP instance: S=[871, 532, 495, 337] t=0 
Found a subset with given sum 
Time taken: 0.0s 
SSP instance: S=[1011, 837, 599, 559] t=599 
Found a subset with given sum 
Time taken: 0.0s 
SSP instance: S=[571, 306, 181, 121] t=0 
Found a subset with given sum 
Time taken: 0.0s 
SSP instance: S=[807, 284, 220, 71] t=1162 
Found a subset with given sum 
Time taken: 0.0s 
('Times succeeded: ', 100) 
('Times failed: ', 0) 

Answer 1

1. Я не думаю, что сумма определена внутри метода try_at_random (я, S, п, т), как уже говорилось в комментарии о строка 41.

2. Где вы используете «экземпляр» в этом выражении «если», вы имеете в виду «я»? Я также не уверен, определен ли там экземпляр.

3. Когда вы возвращаете это «или» (возвращаете instance.try_at_random (S, n-1, t) или instance.try_at_random (S, n-1, tS [n-1])), что вы ожидаете ? Что вы получите, если вы делаете заявление печати перед тем, как вернуться, чтобы посмотреть, что это значит. Я знаю, что вы пытаетесь вызвать его рекурсивно, но между тем, чтобы не использовать «self.try_at_random» и возвращать оператор «или», я не уверен, что это делает.

Удачи вам!