21 lines
516 B
Python
21 lines
516 B
Python
def greedy_thief(weights, values, M, K):
|
|
items = list(zip(weights, values))
|
|
items.sort(key=lambda x: x[1] / x[0], reverse=True)
|
|
cap = M * K
|
|
total_value = 0
|
|
chosen = []
|
|
for w, v in items:
|
|
if w <= cap:
|
|
chosen.append((w, v))
|
|
cap -= w
|
|
total_value += v
|
|
return total_value, chosen
|
|
|
|
|
|
if __name__ == "__main__":
|
|
weights = [2, 3, 4, 5, 9, 7, 3]
|
|
values = [3, 4, 5, 8, 10, 7, 6]
|
|
M = 2
|
|
K = 10
|
|
print(greedy_thief(weights, values, M, K))
|