mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
68 lines
1.8 KiB
Python
68 lines
1.8 KiB
Python
from typing import List
|
|
|
|
def min_count(weights: List[int], max_weight: int):
|
|
if len(weights) == 0:
|
|
return 0
|
|
|
|
weights = sorted(weights, reverse=True)
|
|
|
|
if weights[0] > max_weight:
|
|
return -1
|
|
|
|
|
|
result = 0
|
|
result += weights.count(max_weight)
|
|
weights = list(filter(lambda x: x != max_weight, weights))
|
|
|
|
nums: List[int] = []
|
|
remaining_weights = weights.copy()
|
|
while len(remaining_weights) != 0:
|
|
for (i, num) in enumerate(remaining_weights.copy()):
|
|
print(num, "n:", nums, "r:", remaining_weights, "w:", max_weight, result)
|
|
|
|
# Found perfect match
|
|
if sum(nums) + num == max_weight:
|
|
nums.append(num)
|
|
result += 1
|
|
# Found optimal match, prepare to loop again
|
|
for rm in nums:
|
|
remaining_weights.remove(rm)
|
|
nums = []
|
|
|
|
# Found something closer
|
|
elif sum(nums) + num < max_weight:
|
|
# We tried summing this one before and it failed
|
|
nums.append(num)
|
|
|
|
# Too far
|
|
elif sum(nums) + num > max_weight:
|
|
pass
|
|
|
|
|
|
if len(nums) != 0:
|
|
result += 1
|
|
for rm in nums:
|
|
remaining_weights.remove(rm)
|
|
nums = []
|
|
|
|
|
|
print(weights, result)
|
|
print()
|
|
return result
|
|
|
|
|
|
|
|
if __name__ == "__main__":
|
|
assert min_count([], 1) == 0
|
|
assert min_count([1], 1) == 1
|
|
assert min_count([2, 3, 3, 5], 4) == -1
|
|
|
|
assert min_count([2, 3, 3, 5], 7) == 2
|
|
assert min_count([2, 3, 3, 5], 6) == 3
|
|
assert min_count([2, 3, 3, 5], 5) == 3
|
|
|
|
assert min_count([1, 1, 1, 1], 1) == 4
|
|
assert min_count([1, 1, 1, 1], 4) == 1
|
|
|
|
assert min_count([3, 4, 1, 2, 3, 3, 5, 9], 10) == 3
|