실행 시간 제한 | 메모리 제한 |
---|---|
3 초 | 512 MB |
도둑은 한 가방에 최대한 많은 가치의 물건을 넣고자 합니다.
하지만 도둑의 가방에는 찢어짐을 방지하기 위해 들어갈 수 있는 무게의 제한이 있습니다.
각 물건은 무게와 가치를 가지고 있으며, 도둑은 물건을 통째로 가져갈지 아니면 아예 가져가지 않을지 결정해야 합니다.
도둑이 가져갈 수 있는 물건들의 조합 중 가치의 합을 최대화하기 위해 넣을 수 있는 물건들을 찾는 프로그램을 작성하세요.
입출력 데이터는 다음 순서대로 각 줄마다 값이 입력됩니다.
도둑이 가져갈 수 있는 물건들의 가치의 최대값을 출력하세요.
7 1 3 4 5 1 4 5 7
9
10 2 3 4 5 3 4 5 6
13
500 4 7 5 1 1 3 3 4 8 5 1 8 9 2 9 1 4 4 2 2 1 7 8 8 7 6 2 2 9 8 5 2 5 1 7 7 5 2 6 4 3 6 3 4 5 9 9 9 9 3 5 8 7 8 2 5 1 2 7 2 5 8 6 9 5 6 4 2 9 1 1 7 2 6 1 6 4 4 6 8 4 8 4 2 8 9 2 1 2 5 3 1 9 3 9 7 4 4 4 6 2 5 3 4 4 8 5 7 1 9 8 2 4 5 8 2 4 6 5 4 6 6 4 3 8 4 4 2 8 8 8 4 6 2 4 2 5 4 6 2 8 5 1 1 9 8 8 7 7 3 9 1 2 9 7 1 1 4 2 9 3 9 3 2 5 7 8 9 5 7 8 9 1 5 2 8 8 3 3 4 2 7 4 8 4 3 7 2 9 2 5 1 3 5 1 8 5 5 6 7
497