Subset Sum / Knapsack

Subset Sum

Subset Sum: NP완전에서 아주 직관적인 문제중 하나다. 집합의 부분집합 중에서 그 합이 0인 경우가 존재하면 참이 된다 {-1, 3, -2, 4} -1+3-2=0 이 집합은 참이다. 부분집합의 합이 0이 아니라 특정 수로 정하면 Knapsack 문제가 된다.
Knapsack: 배낭의 용량이 C이고, n개의 물건의 각각의 무게와 가치가 주어질 때, 배낭에 담을 수 있는 최대 가치를 찾는 문제

print("fsd")