다람쥐 옮기기

상자를 이용하여 최다(多)의 다람쥐를 옮겨야 한다.
다음 조건을 만족하며 이동 가능한 최대의 다람쥐의 수는?

1) 박스는 2개이다.
2) 박스는 30kg 이하까지 담을 수 있다.
3) 다람쥐는 총 9마리이다.
4) 다람쥐의 몸무게(kg)는 각각 [12, 9, 9, 22, 12, 8, 5, 2, 3]이다.

 

순열을 이용한 전수조사(brute force)

from itertools import permutations


def solution(weights):
    answer = 0
    for p_weights in permutations(weights):
        start = count = 0
        for _ in range(2):
            in_box = 0
            for i in range(start, 9):
                if (temp := in_box + p_weights[i]) <= 30:
                    count += 1
                    in_box = temp
                else:
                    start = i
                    break
        answer = max(count, answer)
    return answer


print(solution([12, 9, 9, 22, 12, 8, 5, 2, 3]))

 

재귀로....

일단 박스 1개로 확인.. 

def solution(weights, box=30, n=9):
    if box == 0 or n == 0:
        return 0
    if weights[n - 1] > box:
        return solution(weights, box, n - 1)
    elif box >= weights[n - 1]:
        return max(1 + solution(weights, box - weights[n - 1], n - 1),
                   solution(weights, box, n - 1))


print(solution([12, 9, 9, 22, 12, 8, 5, 2, 3])) # 5

확인을 위해 배열로 바꿔서...

def solution(weights, box=[], n=9):
    capacity = 30 - sum(box)
    if capacity == 0 or n == 0:
        # print(box)
        return 0
    if weights[n - 1] > capacity:
        return solution(weights, box, n - 1)
    else:
        return max(1 + solution(weights, box + [weights[n - 1]], n - 1),
                   solution(weights, box, n - 1))


print(solution([12, 9, 9, 22, 12, 8, 5, 2, 3]))

잘 작동 되는 것 같은 느낌인데...

박스 2개로....

def solution(weights, box1=30, box2=30, n=9):
    if (box1 == 0 and box2 == 0) or n == 0:
        return 0
    if weights[n - 1] > box1 and weights[n - 1] > box2:
        return solution(weights, box1, box2, n - 1)
    elif box1 >= weights[n - 1] > box2:
        return max(1 + solution(weights, box1 - weights[n - 1], box2, n - 1),
                   solution(weights, box1, box2, n - 1))
    elif box2 >= weights[n - 1] > box1:
        return max(1 + solution(weights, box1, box2 - weights[n - 1], n - 1),
                   solution(weights, box1, box2, n - 1))
    else:
        return max(1 + solution(weights, box1 - weights[n - 1], box2, n - 1),
                   1 + solution(weights, box1, box2 - weights[n - 1], n - 1),
                   solution(weights, box1, box2, n - 1))


print(solution([12, 9, 9, 22, 12, 8, 5, 2, 3]))

작동 과정을 확인하기 위해...

def solution(weights, box1=[], box2=[], n=9):
    capacity1, capacity2 = 30 - sum(box1), 30 - sum(box2)
    if (capacity1 == 0 and capacity2 == 0) or n == 0:
        # print(box1, box2)
        return 0
    if weights[n - 1] > capacity1 and weights[n - 1] > capacity2:
        return solution(weights, box1, box2, n - 1)
    elif capacity1 >= weights[n - 1] > capacity2:
        return max(1 + solution(weights, box1 + [weights[n - 1]], box2, n - 1),
                   solution(weights, box1, box2, n - 1))
    elif capacity2 >= weights[n - 1] > capacity1:
        return max(1 + solution(weights, box1, box2 + [weights[n - 1]], n - 1),
                   solution(weights, box1, box2, n - 1))
    else:
        return max(1 + solution(weights, box1 + [weights[n - 1]], box2, n - 1),
                   1 + solution(weights, box1, box2 + [weights[n - 1]], n - 1),
                   solution(weights, box1, box2, n - 1))


print(solution([12, 9, 9, 22, 12, 8, 5, 2, 3]))

 

배열을 이용하는 방법도 있지만....