Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/bin/env python3
- # Assignment 3.3
- # Group 7
- # Tobias Schramm & Malte Hansen
- import sys
- # Just a simple container to avoid messing around with too many arrays
- class Lecture():
- def __init__(self, cost, effort):
- self.cost = cost
- self.effort = effort
- budget = 20
- lectures = [Lecture(1, 1), Lecture(2, 1), Lecture(1, 5), Lecture(7, 8), Lecture(3, 7), Lecture(5, 21), Lecture(1, 2), Lecture(4, 4), Lecture(5, 6)]
- print('Number of items: {0}'.format(len(lectures)))
- # Calculate maximum effort and cost
- max_effort = 0
- max_cost = 0
- for l in lectures:
- max_effort += l.effort
- max_cost += l.cost
- print('Maximum possible effort: {0}'.format(max_effort))
- print('Maximum possible cost: {0}'.format(max_cost))
- # Create and init matrix
- M = [[0 for i in range(max_cost + 1)] for j in range(len(lectures))] # Fills matrix with zeroes
- for cost in range(1, max_cost + 1): # for i from 1 to max_cost + 1
- if lectures[0].cost != cost:
- M[0][cost] = max_effort + 1 # Let's use max_effort + 1 as our invalid value
- else:
- M[0][cost] = lectures[0].cost
- # Fill it!
- for i in range(1, len(lectures)):
- lecture = lectures[i]
- for cost in range(1, max_cost + 1):
- if cost < lecture.cost:
- M[i][cost] = M[i - 1][cost]
- else:
- if M[i - 1][cost - lecture.cost] + lecture.effort > M[i - 1][cost]:
- M[i][cost] = M[i - 1][cost]
- else:
- M[i][cost] = M[i - 1][cost - lecture.cost] + lecture.effort
- # Show the matrix because it's pretty
- print('ADS ', end='')
- for i in range(len(lectures)):
- print('{:3d} '.format(i), end='')
- print()
- for j in range(max_cost + 1):
- print('{:3d} '.format(j), end='')
- for i in range(len(lectures)):
- print('{:3d} '.format(M[i][j]), end='')
- print()
- # Get the smallest amount of effort necessary to use all budget
- min_effort = max_effort + 1
- actual_cost = -1
- for cost in reversed(range(budget, max_cost)):
- effort = M[len(lectures) - 1][cost]
- if effort < min_effort:
- min_effort = effort
- actual_cost = cost
- print('Best we can do is an effort of {0} spending {1}'.format(min_effort, actual_cost))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement