배열 번호가 있다고 가정하고 최대 50개의 고유 값이 있습니다. 수량이라는 또 다른 배열도 있습니다. 여기서 수량[i]은 i번째 고객이 주문한 값의 양을 나타냅니다. 다음과 같이 숫자를 분배할 수 있는지 확인해야 합니다.
-
i번째 고객은 정확히 수량[i]개 항목을 얻습니다.
-
i번째 고객이 얻는 가치는 모두 동일하며
-
모든 고객이 만족합니다.
따라서 입력이 nums =[5,1,2,2,3,4,4,3,3] quantity =[2,2,3]과 같으면 두 고객이 두 개의 요소를 원하기 때문에 출력은 True가 됩니다. 각각 [2,2]와 [4,4]를 얻을 수 있도록 하고, 세 번째는 3개의 항목을 원하고 [3,3,3]을 얻을 수 있으므로 모두 만족합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
util() 함수를 정의합니다. 이것은 i, cntr이 걸립니다
-
i가 수량의 크기와 같으면
-
참을 반환
-
-
temp_counter :=cntr 사본 만들기
-
cntr의 각 cnt에 대해 수행
-
cnt>=수량[i]이면
-
temp_counter[cnt] :=temp_counter[cnt] - 1
-
temp_counter[cnt]가 0과 같으면
-
temp_counter에서 cnt 번째 요소 삭제
-
-
rem :=cnt - 수량[i]
-
temp_counter[rem] :=temp_counter[rem] + 1
-
util(i+1, temp_counter)이 참이면
-
참을 반환
-
-
temp_counter[rem] :=temp_counter[rem] - 1
-
temp_counter[rem]이 0과 같으면
-
temp_counter에서 rem-th 요소 삭제
-
-
-
temp_counter[cnt] :=temp_counter[cnt] + 1
-
-
거짓을 반환
-
기본 방법에서 다음을 수행하십시오.
-
cnt :=nums에 존재하는 모든 숫자의 빈도에 대한 맵 보유 빈도
-
수량을 역순으로 정렬
-
반환 유틸리티(0, cnt)
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from collections import Counter
def solve(nums, quantity):
def util(i, cntr):
if i == len(quantity):
return True
temp_counter = cntr.copy()
for cnt in cntr:
if cnt >= quantity[i]:
temp_counter[cnt] -= 1
if temp_counter[cnt] == 0:
temp_counter.pop(cnt)
rem = cnt - quantity[i]
temp_counter[rem] += 1
if util(i+1, temp_counter):
return True
temp_counter[rem] -= 1
if temp_counter[rem] == 0:
temp_counter.pop(rem)
temp_counter[cnt] += 1
return False
cnt = Counter(Counter(nums).values())
quantity.sort(reverse=True)
return util(0, cnt)
nums = [5,1,2,2,3,4,4,3,3]
quantity = [2,2,3]
print(solve(nums, quantity)) 입력
[0,1,2,3,4], [[3,1],[1,3],[5,6]]
출력
True