Scale 문제

알고리즘에서, 무게를 가지는 추 n개를 가지고, M의 무게의 무게를 맞출수 있다면, 이를 Scale이 가능하다고 합니다.

 

이번 알고리즘은 주어진 n개의 추를 가지고 무게 M을 Scale할 수 있는지를 확인하는 알고리즘 입니다.

 

 

위와같은 상황에서 4개의 추 가지고 12를 만들 수 있을까요?

이런 상황에선 간단하게 12 = 5+7 또는 4+1+7의 조합으로 가능한 것을 알 수 있습니다.

 

하지만 M이 커지고, 추의 개수가 증가하면 그 조합을 모두 확인하기란 어렵습니다.

 

 

이제 Scale 가능 여부를 확인하는 알고리즘을 보겠습니다.

 

무게 Wx인 추를 추가하여, 무게 k를 측정할 수 있는지 여부를 알기 위해선

 

1. W1~W(x-1)의 추를 가지고 k-Wx(=Wx가 추가되기 전 무게)를 측정할 수 있는지 여부와

2. W1~W(x-1)의 추를 가지고 k를 측정할 수 있었는지 여부

 

둘중 하나라도 만족한다면, W1~Wx의 추를 가지고 무게 k를 측정할수 있음을 알 수 있습니다.

Wx무게의 추를 추가하였을 때 무게 k를 scale할 수 있는지 없는지 예시(위 경우에는 scale이 가능)

 

이때, 2개의 경우의 답을 알기위해서는 W(x-1)Case를 보고, 거슬러 올라가 최종적으로 W1의 Case를 확인하게 됩니다.

=============================================

※이번 알고리즘에서는 대 전제가 필요합니다.

1. 0의 무게를 Scale하는것은 가능하다

2. 0보다 작은 무게는 scale하는것이 불가능하다.

3. 0을 제외, 어떤 무게M도 무게0의 추로는 Scale안된다.

=============================================

그럼 W1의 경우를 보겠습니다.

1. W0(= 무게가 0)의 추를 가지고 k-W1를 측정할 수 있는지 여부

   -> 이때 k와 W1가 같으면, 대 전제에 의해서 Scale이 가능한 것을 알수있습니다.

2. k를 측정할 수 있는지 여부

  -> 무게 0인 추를 가지고 측정할 수 없기 때문에 불가능합니다.

 

이제 S(d,k)를 d개의 추 가지고 k의 무게를 scale할 수 있는가로 정의하고, 가능하면 1, 불가능하면 0 이라고한다면

 

S(d,k) = Max(S(d-1, k), S(d-1, k-W(d-1))이 되게됩니다.

 

이제 k를 0~M까지, d를 1~n까지 전개하여 점화식을 풀면,

최종적으로 M의 무게를 갖는 물체를 n개의 추로 무게를 측정할 수 있는지 여부를 알수 있게됩니다.

 

import random
import copy
#무게 M에 해당하며, 10~20사이 랜덤하게 할당
weight = random.randint(10,20)
#1~7 사이 추를 랜덤하게 5개 생성
token = [random.randint(1,7) for i in range(5)]


def scale_availability(M_weight, M_token):    
    #이전 Weight의 추에대한 Scale 가능한 무게를 기록한 List
    weight_table = [1] + [0 for i in range(M_weight)]
    route_save = copy.deepcopy(weight_table)
    #이번 Weight의 추에대한 Scale 가능한 무게를 기록한 List
    weight_table_2 = [1] + [0 for i in range(M_weight)]    
    #j = 추의 개수
    for j in range(len(M_token)):
        #1~weight까지 계측 가능 여부 측정        
        for i in range(M_weight):
            #1~d-1번째 추를 가지고 무게 k를 측정할 수 있는지 여부
            a = weight_table[i+1]
            #1~d-1번째 추를 가지고 무게 k-Wd를 측정할 수 있는지 여부
            if (i+1)-M_token[j]<0:
                b = 0
            elif (i+1)-M_token[j]>=0:
                b = weight_table[(i+1)-M_token[j]]                
            weight_table_2[i+1] = max(a,b)    
        #해당 Weight의 추를 사용한 결과 Scale가능한 무게들을 기록합니다.
        route_save.append(weight_table_2)
        weight_table = copy.deepcopy(weight_table_2)
        weight_table_2 = [1] + [0 for i in range(M_weight)]
    return True if weight_table[M_weight] == 1 else False, route_save

#scale 가능 여부를 True or False로 반환
# + 어떤 조합으로 Scale이 가능한지 확인 가능한 Table반환
scale_availability(weight, token)