SHARE
TWEET

Untitled

a guest Nov 16th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python2.7
  2. # -*- coding: utf-8 -*-
  3. '''
  4. Assignment 1, Problem 1: Birthday Present
  5.  
  6. Team Number:
  7. Student Names:
  8. '''
  9.  
  10. '''
  11. Copyright: Pierre.Flener@it.uu.se and his teaching assistants, 2019.
  12.  
  13. This file is part of course 1DL231 at Uppsala University, Sweden.
  14.  
  15. Permission is hereby granted only to the registered students of that
  16. course to use this file, for a homework assignment.
  17.  
  18. The copyright notice and permission notice above shall be included in
  19. all copies and extensions of this file, and those are not allowed to
  20. appear publicly on the internet, both during a course instance and
  21. forever after.
  22. '''
  23.  
  24. import unittest
  25. import numpy as np
  26.  
  27.  
  28.  
  29. def birthday_present(P, n, t):
  30.     '''
  31.     Sig:  int[0..n-1], int, int --> Boolean
  32.     Pre:
  33.     Post:
  34.     Ex:   P = [2, 32, 234, 35, 12332, 1, 7, 56]
  35.           birthday_present(P, len(P), 299) = True
  36.           birthday_present(P, len(P), 11) = False
  37.     '''
  38.     # Initialise the dynamic programming matrix, A
  39.     # Type: Boolean[0..n][0..t]
  40.     A = [[None for i in range(t + 1)] for j in range(n + 1)]
  41.  
  42.     # T = 0 => True
  43.     for i in range(n + 1):
  44.         A[i][0] = True
  45.  
  46.     # N = 0, T > 0 => False
  47.     for i in range(1,t+1):
  48.         A[0][i] = False
  49.  
  50.     # Go through matrix
  51.     for i in range(1, n + 1):
  52.         for j in range(1, t + 1):
  53.             # Sum < number => same as previous
  54.             if j < P[i - 1]:
  55.                 A[i][j] = A[i - 1][j]
  56.             # Sum >= number => can use it
  57.             if j >= P[i - 1]:
  58.                 # Not use number or use number
  59.                 A[i][j] = (A[i - 1][j] or A[i - 1][j - P[i - 1]])
  60.    
  61.    
  62.     return A[n][t]
  63.  
  64.  
  65. def birthday_present_subset(P, n, t):
  66.     '''
  67.     Sig:  int[0..n-1], int, int --> int[0..m]
  68.     Pre:
  69.     Post:
  70.     Ex:   P = [2, 32, 234, 35, 12332, 1, 7, 56]
  71.           birthday_present_subset(P, len(P), 299) = [56, 7, 234, 2]
  72.           birthday_present_subset(P, len(P), 11) = []
  73.     '''
  74.     A = [[None for i in range(t + 1)] for j in range(n + 1)]
  75.  
  76.     # T = 0 => True
  77.     for i in range(n + 1):
  78.         A[i][0] = True
  79.  
  80.     # N = 0, T > 0 => False
  81.     for i in range(1,t+1):
  82.         A[0][i] = False
  83.  
  84.     # Go through matrix
  85.     for i in range(1, n + 1):
  86.         for j in range(1, t + 1):
  87.             # Sum < number => same as previous
  88.             if j < P[i - 1]:
  89.                 A[i][j] = A[i - 1][j]
  90.             # Sum >= number => can use it
  91.             if j >= P[i - 1]:
  92.                 # Not use number or use number
  93.                 A[i][j] = (A[i - 1][j] or A[i - 1][j - P[i - 1]])
  94.  
  95.     # Go through matrix again but in to get sum
  96.     #for i in xrange(1, n + 1, -1):
  97.      #   for j in xrange(1, t + 1, -1):
  98.       #      if j == True:
  99.    
  100.     auxboi = n
  101.     auxT = t
  102.     newP = []
  103.  
  104.     if A[n][t] is False:
  105.         return newP
  106.     else:
  107.         #loop stops when A[0][t] is reached
  108.         while auxboi > -1:
  109.             # if the element is True move "up" on step in the matrix
  110.             if A[auxboi][auxT] == True:
  111.                 print "NOT ADD", A[auxboi][auxT], auxboi, auxT
  112.                 auxboi = auxboi - 1
  113.             # if the current element in the matrix is False
  114.             # add the value of the element in p[auxboi]
  115.             # subtract the value of p[auxboi] from auxT
  116.             # to jump to the next possible value in the subset
  117.             if A[auxboi][auxT] == False:
  118.                 print "ADD", A[auxboi][auxT], auxboi, auxT
  119.                 newP.append(P[auxboi])
  120.                 print newP
  121.                 auxT = auxT - P[auxboi]
  122.                 print "auxT is", auxT
  123.  
  124.  
  125.     return newP      
  126.      
  127.  
  128.    
  129.  
  130.  
  131.  
  132.  
  133.  
  134. if __name__ == '__main__':
  135.     P = [2, 32, 234, 35, 12332, 1, 7, 56]
  136.     n = len(P)
  137.     t = 11
  138.     print(birthday_present_subset(P, n, t))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top