기본적인 0/1 배낭 문제 및 그 변형

12895. 평범한 배낭

평범 그 자체인 가장 기본적인 0/1 배낭 문제다.

를 i번 물건까지 사용할 수 있을 때, 무게 합이 j일 때의 최대 가치라고 정의하자.

가 되고, 어렵지 않게 해결할 수 있다. 시간복잡도는 다.

14305. Stretch Rope

0/1 배낭 문제에서 한 배낭의 무게가 라는 범위로 표현되는 문제다.

마찬가지로 를 i번 물건까지 사용할 수 있을 때, 무게 합이 j일 때의 최소 가치라고 정의해서 해결할 수 있다.

그냥 무작정 dp를 돌리면 시간복잡도가 이어서 시간 초과가 난다.

핵심 아이디어는 해당 물건을 사용해서 무게 합이 j가 되게 하려면, 기존 무게 합이 에 포함되어야 한다는 것이다. 이 구간은 j가 증가함에 따라 오른쪽으로 이동하는 구간이고, 고로 데크를 이용한 슬라이딩 윈도우로 구간 최솟값을 구하는 테크닉을 사용하면 시간복잡도를 로 줄일 수 있다.

12920. 평범한 배낭 2

이번에는 한 물건을 각 물건마다 주어진 한도 내에서 여러번 사용할 수 있다. 이런 문제를 0/K 배낭 문제라고 한다.

가장 단순한 방법은 물건을 K개 만드는 방법이고, 시간복잡도는 로 매우 느리다.

이 방법을 해결하는 첫 번째 방법은 굳이 K개를 다 만들 필요가 없단 것을 깨달으면 알 수 있는데, 2진법의 논리에서 생각을 해 본다면 K=12일때는 1개, 2개, 4개, 12-(1+2+4)=5개에 해당되는 물건들만 만들어도 1개부터 12개까지의 모든 방법을 표현할 수 있다는 것을 알 수 있다. 이 방법을 일반화하면 각 물건마다 logK개 만큼의 물건만 만들어도 되고, 시간복잡도는 다.

이 방법과는 완전히 다른 방법으로 접근한다면, 더욱 빠르게 이 문제를 해결할 수 있다. 이번 방법의 핵심은 어떠한 무게 합 j가 되게 하는 기존 무게 합은 W[i]로 나눈 나머지가 같다는 것이다. 결국, 우리는 W[i]로 나눈 나머지에 따라서 무게 합들을 나누어서 해결할 수 있다. W[i]로 나눈 나머지가 같은 무게 합들에 대해서, j가 될 수 있게 하는 무게 합들은 앞 K개의 무게 합들이다. 기존 무게 x의 W[i]로 나눈 나머지가 같은 무게 합들의 배열 상 위치를 p, j의 위치를 q라고 하자. x에서 j로 넘어간다면, dp값은 이 되고, q에 의한 부분을 제외하면 x를 나타내는 값은 로 일정하다. 결국 우리는 K칸 앞까지의 값들 중 최댓값을 알아야 하고, 이는 14305번처럼 데크를 이용한 슬라이딩 윈도우를 통해서 해결할 수 있다. 시간복잡도는 이다.