무한 배낭 문제 unbounded knapsack에 대한 또 다른 핵심 고찰(dp[i] = min(dp[i], dp[i-k*w[j]] + k*v[j]) = min(dp[i], dp[i-w[j]] + v[j]))

1. 무한 배낭 문제(unbounded knapsack)

 

일반적인 배낭 문제는 무게가 제한된 배낭에 특정 물건을 최대 가치로 담는 방법을 찾는 문제인데,

 

각각의 물건은 최대 하나씩만 담을 수 있다

 

https://deepdata.tistory.com/474

배낭(Knapsack) 문제, 다이나믹 프로그래밍 해법 배우기

 

 

근데 각 물건을 무한히 담을 수 있는 경우, 그러한 문제를 unbounded knapsack 무한 배낭 문제라고 부른다

 

알고보니 이미 이 문제에 대한 해법을 공부했던데?

 

 

https://deepdata.tistory.com/1286

0-1 knapsack 배낭 문제 해법 반드시 알아야하는 디테일(물건을 중복해서 담는 경우)

 

 

1차원 배열로 해결할 때 무게를 역방향으로 순회하면 물건 하나씩만 담기고

 

무게를 정방향으로 순회하면 물건을 중복해서 담을 수 있다는거

 

근데 이런 문제를 오랜만에 풀어서 그런가?

 

이런 오류에 빠진 적이 있었다

 

 

2. 문제

 

1660번: 캡틴 이다솜

 

대충 요약하면 어떤 사면체를 만들 수 있는 포탄의 개수는

 

1개, 4개, 10개, 20개, ...이다.

 

1개짜리로 만든 사면체, 4개짜리로 만든 사면체,, ... 이렇게 가능하다는거

 

이때, n개의 대포알이 주어질때 가능한 사면체의 최소 개수를 구하는 문제

 

즉 바꿔 생각하면 

 

1개짜리 사면체 a개, 4개짜리 사면체 b개, 10개짜리 사면체 c개,...

 

a + 4b + 10c + ... = n이 될 수 있는 a+b+c+...의 최솟값을 찾는 문제

 

크기가 n인 배낭에 각각의 사면체를 무한히 담을 수 있는 무한 배낭 문제이다.

 

n이 최대 30만이기 때문에 O(N)정도에 해결해야한다

 

다행히 가능한 사면체의 종류를 먼저 구해보면

 

1

3

6

10

...

 

으로 계차수열이 2,3,4,...인 형태이며

 

1,4,10,20,...으로 누적합으로 구해보면... 약 120가지

 

n = 120

dp = [0]*(n+1)

dp[1] = 1

for i in range(2,n+1):
    
    dp[i] = dp[i-1] + i

for i in range(2,n+1):
    
    dp[i] += dp[i-1]

print(dp[-1])
295240

 

 

이러면 dp에는 가능한 사면체의 종류가 1,4,10,20,...으로 구해져있다

 

그러면 이제 여기서 배낭문제를 해결하듯이 해결할려고 시도했는데

 

담을 수 있는 물건 dp[1],dp[2],dp[3],...dp[120]에 대하여 가능한 포탄의 개수 1,2,3,...,N 각각에 대해 

 

각 물건 dp[j]는 각 포탄의 개수 i에 대하여 최대 몇개까지 담을 수 있나?

 

1부터 i//dp[j]개까지 담을 수 있을 것

 

그러면 이런 식으로 삼중 루프를 돌게 된다

 

이때 최소 dp[1] = 1이고 N의 최대는 30만이라 O(N^2)정도가 된다

 

for j in range(1,120):
    
    for i in range(1,N+1):
    
        for k in range(1,i//dp[j]+1):
            
            dp2[i] = min(dp2[i], dp2[i - k*dp[j]] + k)

 

 

근데 점화식을 잘 보면

 

dp2[i] = min(dp2[i], dp2[i-dp[j]] + 1, dp2[i-2*dp[j]] + 1 * 2, dp2[i-3*dp[j]] + 1*3, dp2[i - 4*dp[j]] + 1*4 + ..., dp2[i - k*dp[j]] + 1*k,...)

 

여기서 dp2[i - dp[j]]를 써보면

 

dp2[i - dp[j]] = min(dp2[i - dp[j]], dp2[i - dp[j] - dp[j]] + 1, dp2[i - dp[j] - 2dp[j]] + 2, ... dp2[i - dp[j]] - (k-1)dp[j]] + k-1,...)

따라서, 

dp2[i] = min(dp2[i], 

 

min(dp2[i - dp[j]], dp2[i - dp[j] - dp[j]] + 1, dp2[i - dp[j] - 2dp[j]] + 2, ... dp2[i - dp[j]] - (k-1)dp[j]] + k-1,...) + 1,

 

dp2[i-2*dp[j]] + 1 * 2, dp2[i-3*dp[j]] + 1*3, dp2[i - 4*dp[j]] + 1*4 + ..., dp2[i - k*dp[j]] + 1*k,...)

)

 

dp2[i] = min(dp2[i], 

 

min(dp2[i - dp[j]] + 1, dp2[i - 2dp[j]] + 2, dp2[i - 3dp[j]] + 3, ... dp2[i - kdp[j]] + k,...),

 

dp2[i-2*dp[j]] + 1 * 2, dp2[i-3*dp[j]] + 1*3, dp2[i - 4*dp[j]] + 1*4 + ..., dp2[i - k*dp[j]] + 1*k,...)

)

 

dp2[i - 2dp[j]] + 2, dp2[i - 3dp[j]] + 3, ... dp2[i - kdp[j]] + k 과

 

dp2[i-2*dp[j]] + 1 * 2, dp2[i-3*dp[j]] + 1*3, dp2[i - 4*dp[j]] + 1*4 + ..., dp2[i - k*dp[j]] + 1*k 이 중복되어 있다

 

dp2[i-dp[j]]의 계산에는 이미 min( dp2[i-2*dp[j]] + 1 * 2, dp2[i-3*dp[j]] + 1*3, dp2[i - 4*dp[j]] + 1*4 + ..., dp2[i - k*dp[j]] + 1*k) 을 계산했던 것이다

 

 

그래서, dp2[i] = min(dp2[i], dp2[i - dp[j]] + 1)로 줄일 수 있다.

 

일반적으로 dp[i] = min(dp[i], dp[i - k*W[j]] + V[j]*k) = min(dp[i], dp[i - W[j]] + V[j])로 할 수 있다

 

 

for j in range(1,120):
    
    for i in range(1,N+1):
        
        dp2[i] = min(dp2[i], dp2[i - dp[j]] + 1)

 

 

이러면 약 O(N)에 해결할 수 있게 된다.

 

n = 120

dp = [0]*(n+1)

dp[1] = 1

for i in range(2,n+1):
    
    dp[i] = dp[i-1] + i

for i in range(2,n+1):
    
    dp[i] += dp[i-1]

N = int(input())

INF = 10**12

dp2 = [INF]*(N+1)
dp2[0] = 0
    
for i in range(1,n+1):
    
    for j in range(dp[i],N+1):
        
        dp2[j] = min(dp2[j], dp2[j-dp[i]] + 1)

print(dp2[N])

 

 

중복해서 담아야하기 때문에, 역방향으로 순회하면 틀리게 된다

 

for i in range(1,n+1):
    
    for j in range(N,dp[i]-1,-1):
        
        dp2[j] = min(dp2[j], dp2[j-dp[i]] + 1)