N cướp, mỗi người cần time[i] phút để cướp. Vệ sĩ quay lại sau G phút. Tối đa 2 cướp cùng lúc trong kho. Kiểm tra xem có thể sắp xếp để tất cả cướp xong trước khi vệ sĩ đến không.
Ví dụ: N=3, G=5, time=[3,5,2] → True.
Giải thuật
- Nếu sum(time) > 2G: False.
- Nếu sum(time) ≤ G: True.
- Ngược lại: bài toán balo (subset sum) để tìm tập con có tổng ≤ G và lớn nhất. Nếu sum(time) - max_subset_sum ≤ G → True.
Ví dụ mã Python
def solve(N, G, time):
total = sum(time)
if total > 2 * G:
return False
if total <= G:
return True
valid = [False] * (G + 1)
valid[0] = True
for x in time:
for i in range(G, -1, -1):
if i - x >= 0 and valid[i - x]:
valid[i] = True
max_subset = max(i for i, v in enumerate(valid) if v)
return total - max_subset <= G
N = 3
G = 5
time = [3, 5, 2]
print(solve(N, G, time)) # Output: True
Đầu vào
3, 5, [3,5,2]
Đầu ra
True