https://www.acmicpc.net/problem/12865

참고 사이트 : https://howudong.tistory.com/106

위 참고 사이트의 도움을 받아 겨우 이해할 수 있었다.. (누군지 모르지만 정말 감사합니다..)

다만 그 내용을 나한테 조금 맞게 바꾸어서 다시 정리해 보겠다.

예제 입력1을 중심으로 설명해보도록 하겠다.

4개의 물건이 있고 순서대로 번호가 매겨진다고 해보자. 물건에는 무게와 가치가 있다. 번호(무게,가치) 이런식으로 표현하자면,

1(4,13), 2(4,8), 3(3,6), 4(5,12)이다. 이 물건들 중에서 물건을 골라서 가치가 얻을 수 있는 최대 가치를 구하는데 그 물건들의 총 무게가 7을 넘으면 안 된다.

어텋게 풀지?

처음 생각할 수 있는 방법은 완전탐색이다. 4개의 물건 중에서 물건을 고르는 것이므로 4개의 원소가 있는 집합의 부분집합을 탐색하는 방식으로 값을 구할 수 있다.