给一组数列，若数列内存在一个数等于数列内其他一些数的和，则去除那些数。此删除操作可重复操作直到无法继续找到满足条件的数进行删除。请写出一个函数，输入为整型数组，经过函数内一系列删除操作后得到一个最短数组，返回最短数组的长度。
比如{48，20，1，3，4，6，9，24}由于(4+20+24=48)所以去除4，20，24，48，余下{1,3,6,9}后，由于3+6=9，去除{3,6,9}得到{1}，由于数组长度为1，返回1
ringa_lee2017-04-17 15:39:03
이 문제는 NPC의 육안 검사를 통해 해결됩니다. "두 단계"로 나눌 수 있습니다.
"추가 하위 집합"을 모두 찾습니다. 각 요소를 가능한 합으로 취하고 부분 집합 합 알고리즘을 사용하여 하나씩 해결합니다.
상호 배타적인 덧셈 부분 집합의 최대 합집합을 찾습니다. 집합 패킹 알고리즘을 참조하고 선형 프로그래밍을 사용하여 이를 해결합니다.
다음은 Mathematica를 사용하여 알고리즘을 자세히 설명합니다.
집합의 덧셈 공식을 구성하는 모든 숫자를 열거하려면(음수 및 반복 숫자 허용) 먼저 하위 집합 합계 알고리즘(캐시를 사용한 재귀)을 사용하여 합계가 주어진 숫자인 하위 집합을 열거합니다.
으아악 코드는 q을 재귀적으로 호출하고 결과를 캐시합니다. 특정 재귀 파생에 대해서는 이 질문을 참조하세요. 계산된 덧셈 하위 집합은 내부적으로 정렬되고 마지막으로 중복된 항목을 제거하기 위한 합집합 작업이 수행됩니다. 사용 사례:
주어진 숫자는 이 문제의 집합에 있는 임의의 요소일 수 있으므로 subsetSum를 사용하여 집합의 각 요소를 반복하고 해당 요소와 나머지 요소를 사용하여 덧셈을 만들어 보세요. 마지막으로, 가능한 총 추가 하위 집합인 중복 조합이 제거됩니다.
위 코드는 집합에 대한 내부 정렬 작업도 수행합니다. 집합에 합계와 합계를 추가할 때 순서가 흐트러질 수 있기 때문입니다. 그리고 가수 개수가 2개 미만인 경우는 삭제한다. 사용 사례:
으아악추가 부분 집합을 얻은 후 가중치 집합 패킹을 사용하여 상호 배타적인 최대 합집합을 찾습니다. 이를 선형 프로그래밍 언어로 표현하려면
$$array{text{maximize} & sum{|s_i| 세트는 상호 배타적입니다} \ & x_i in {0, 1} & text{$x_i=1$, 그런 다음 세트 $i$를 선택하고, 그렇지 않으면 세트를 포기합니다. $i$}}$$
Mathematica는 내장된 LinearProgramming 기능을 제공합니다.
질문 예:
16개 요소 세트를 무작위로 생성합니다.
pickSumList로 결과를 찾고 합계 요소를 강조 표시합니다.
나머지 요소:
