[백준]12920 평범한 배낭 2

K_Gs·2022년 4월 20일
0

BOJ

목록 보기
9/13
post-thumbnail

[정답이 아니라 풀이 기록입니다.]

평범한 배낭 2

w의 무게제한이 있는 배낭이 있다. n개의 물건이 있고, 각 물건은 Vi의 가치, Wi의 무게를 지니고, 총 Ki개가 있다. 각 물건을 개수 내에서 여러개 챙길 수 있을 때, 최대 이익을 구하시오.

접근

  1. 각 물건 k개 중 몇개를 챙길지 고려해야합니다.
  2. 나머지는 일반 냅색과 같습니다.

구현

일반 냅색

일반 냅색은 시간 복잡도가 O(nm)입니다.
만약 이 문제 - (링크) 와 같이 각 위치에서 물건을 몇 개 챙길지 for을 통해 고려한다면 시간복잡도가 O(nmk)가 됩니다.

n이 최대 100, m이 최대 1만 그리고 각 물건이 무게가 1일경우 최대 k가 1만이기에
O(nmk)는 시간초과가 발생합니다.

0~k개

하나의 물건이 k개 있다면 각 위치에서 그 물건을 0~k개 챙기는 경우를 고려해야합니다.
0~k를 표현하는 방법을 생각해봅시다.
(저는 못 떠올렸습니다.)

1이 있다면 0~1을 표현할 수 있습니다.{ {} , {1} }
여기에 2가 더해진다면 0~3을 표현할 수 있습니다.{ {} , {1} , {2} , {1,2} }
여기에 4가 더해지면 0~7을 표현할 수 있습니다.{ {} , {1} , {2} , {1,2} , {4} , {1,4} , {2,4} , {1,2,4} }
...

하나의 물건 k개을 1,2,4,8... 이런 식으로 묶어서 분할하면 됩니다.
만약 2개 묶음과 4개 묶음을 챙기면 6개를 챙긴게 되는거죠!
그리고 이렇게 하면 각 위치에서 몇개를 챙길지 고려하는게 아니라 이 묶음을 챙길지 말지를 고려하는 일반 냅색으로 풀 수 있게 됩니다.

물건 묶기

물건을 묶는 방법은 간단합니다.

물건의 가치를 v, 무게를 w, 개수를 k라 하겠습니다.
임의의 변수 Count를 1로 초기화 해두고 만약 k가 Count보다 크다면 {v*Count,w*Count}로 물건리스트에 추가합니다.
그리고 k에서 Count를 빼주고 Count*=2를 해줍니다.
k가 Count보다 작아질 때까지 이것을 반복합니다.
만약 k가 0이라면 종료하고 아닐경우에는 {v*k,w*k}로 물건리스트에 추가해주고 종료합니다.

물건을 여러개로 묶었으니 당연히 가치와 무게도 묶은 수 만큼 늘어납니다.

마지막에 k가 0이 아닐 경우 무게와 가치에 k를 곱해 물건리스트에 추가하는 데, 이는 1 ~ (2^t)-1까지(t는 임의의 정수) 표현 가능한 상태에서 (2^t) ~ k까지를 표현 가능하게 하기 위해 넣어주는 것입니다.

코드로는 아래와 같습니다.

//ll == long long
typedef struct item {
	ll w;
	ll v;

	item(){
		w = 0;
		v = 0;
	}
	item(ll a,ll b) : w(a), v(b) {}
};
//------------------------
scanf("%lld%lld%lld",&a,&b,&c);//v,w,k
ll Count = 1;
ll temp =0;
while (c > 0) {
	temp = min(Count,c);//k와 count중 작은걸 취함
	list[++Ic] = item(a*temp,b*temp);//물건리스트에 추가
	c-=temp;//k에서 빼줌
	Count*=2;//count*=2

}

k가 최대 1만이기에 물건리스트는 하나의 물건에서 최대 14개(13개 + 나머지 1개) 추가 될 수 있습니다.
물건이 최대 100개이니 리스트의 최대는 1400개입니다.

ll dp[10001][1401];
item list[1401];

답 구하기

이제 일반 냅색을 돌리면 됩니다.

for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= Ic; j++) {
			if (i - list[j].w >= 0) {//이 묶음을 챙길 수 있다면
				dp[i][j] = max(dp[i][j - 1], dp[i - list[j].w][j - 1] + list[j].v);
 				//이 묶음을 챙기는 것과 안챙기는 것 중 더 이득인 것을 취함
			}
			else {//이 묶음을 챙길 수 없다면
				dp[i][j] = dp[i][j-1];
                //이전의 이득 값을 가져옴
			}
		}
}
printf("%lld",dp[m][Ic]);//답 출력

이렇게 해둔다면 시간 복잡도는 O(nmlogk)일 것 같네요.

마무리

다른 분이 질문하신 걸 보고 알았는데, 물건을 분할한다는 건 상상도 못했습니다.
이렇게 또 하나 알아갑니다.

profile
~(~o~)~

0개의 댓글