Page MenuHomec4science
Files F93785309

santa.py
No OneTemporary
Actions

File Metadata

Created
Sun, Dec 1, 11:58

santa.py
View Options

#!/usr/bin/python3
import sys
from io import StringIO
# K = categories size array
# W = weights matrix
# H = happinesses matrix
# from the principle of rod-cutting
def max_happiness(K, W, H, m):
k = len(K)
h = [[0 for x in range(m+1)] for x in range(k+1)] # happiness storage, preallocate of size k * m, there are k_j possible values inside
# compute all possibilities
for j in range(1, k+1):
# loop over possible sizes
for s in range(1, m+1):
maxoverl = 0
# find max over category element
for l in range(K[j-1]):
h_jl = H[j-1][l]
w_jl = W[j-1][l]
if w_jl <= s:
maxoverl = max(h_jl + h[j-1][s - w_jl], maxoverl)
#print("Examined h[%d][%d]: %d" % (j-1, s - w_jl, h[j-1][s - w_jl]))
#print("l = %d, Max over l: %d" % (l, maxoverl))
h[j][s] = max(maxoverl, h[j-1][s])
"""
print()
print("#### FINAL ####")
print("h[%d][%d]: %d" % (j, s, h[j][s]))
print("Max over l: ", maxoverl)
print()
print()
"""
"""
for j in range(k+1):
print(h[j])
"""
# select solution
r = 0
s = m
while r == 0 and s > 0:
for j in range(k, 0, -1):
if h[j - 1][s] != h[j][s]:
r = max(r, h[j][s]) # take optimal
s -= 1
return (r, s+1)
def parse_input(fstream):
# first line treating
first = fstream.readline()
first = first.split(' ') # space separated
if len(first) != 3:
raise Exception("First line should be a 3-spaced set of 3 variables")
n = int(first[0])
m = int(first[1])
k = int(first[2])
H = []
W = []
K = []
# parse other lines
for i in range(k):
line = fstream.readline()
S = line.split(' ') # space separated variables
K.append(int(S[0]))
del S[0] # should be constant as linked list
# convert all in integers
for i in range(len(S)):
S[i] = int(S[i])
W.append(S[::2]) # odd
H.append(S[1::2]) # even
return (K, W, H, m)
# test execution
import sys
#args = sys.argv
#if len(args) < 2:
# print("More arguments plz")
# sys.exit(1)
#input_text = args[1]
# two options, load by string
#fstream = open(filename, 'r')
(K, W, H, m) = parse_input(sys.stdin)
#fstream.close()
(h,w) = max_happiness(K, W, H, m)
print(h)
#print("With a mass %d <= %d, the maximum achievable happiness is %d" % (w, m, h))

Event Timeline

c4science · Help