ads-3_3.py

#!/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))