• API
• FAQ
• Tools
• Archive
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.

Top