다이나믹 프로그래밍을 이용한 partition minimum sum of difference of two subset(합의 차이가 최소가 되는 분할) 문제 해법

1. 문제

 

배열 A가 주어질때, A를 2개의 부분집합으로 분할하고자 하는데, 각 부분집합의 원소의 합이 X,Y이면 abs(X-Y)가 최소가 되도록 분할하고자 한다

 

이때, 그 최솟값을 구하거나 X,Y를 구하는 문제

 

A의 원소의 합이 total = sum(A)라면, 두 부분집합의 원소 합의 차이가 최소가 되는 것은 정확히 절반이 되는 경우이다.

 

그러니까 최대 target = total//2에 도달하는게 가장 좋다.

 

1) dp[i] = A의 원소를 일부 골라서 합했을때, i가 될 수 있는가?

 

만약 i-w를 만들 수 있다면, w를 더하면 i가 될 수 있으므로 dp[i-w] = 1이면 dp[i] = 1이 된다.

 

#dp[i] = 배열 v의 원소를 일부 골라 합해서 i를 만들 수 있는가?
target = total//2

dp = [0]*(target+1)
dp[0] = 1

for w in v:
    
    for i in range(target,w-1,-1):
        
        if dp[i-w] == 1: #i-w가 될 수 있다면,
            
            dp[i] = 1 #i-w에 w를 더하면 i가 될 수 있다.

 

 

O(N*target)정도 시간이 걸리므로, target,N이 너무 크지 않을 때만 가능하다.

 

너무 크면 상당히 어려운 문제가 된다

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

배열 v의 원소 w에 대하여, 모든 가능한 합 i = w~target에 대해 조사해서 i-w를 만들 수 있다면, w를 더하면 i를 만들 수 있다

 

코드를 하나하나 따라가보면 완전탐색인데 효율적으로 하는 완전탐색임을 느낄 수 있다

 

[3,7,9,11,12]라고 할때, 합이 42인데, 절반 21에 대하여 dp[0] = 1로 두고

 

원소 3에 대하여 21부터 3까지 순회해서 dp[0] = 1이니까 dp[3] = 1로 만들 수 있다. 

 

실제로 3을 골랐으니 3을 만들 수 있다

 

다음 7에 대하여 [3,7]만 보면 3, 7, 10 3가지를 만들 수 있는데 단순하게 하면 3을 골라보고 7을 골라보고 3,7을 골라봐야해서 어렵잖아

 

이전에 3을 만들어서 dp에 저장해놔가지고

 

21부터 3을 순회할때, dp[10-7] = dp[3] = 1이므로 dp[10] = 1이 된다. 

 

이미 3을 만들어 놨으니까 7을 넣기만 하면 10을 만들 수 있게 된다

 

그리고 dp[7-7] = dp[0] = 1이므로 dp[7] = 1이 된다. 

 

이미 dp[3] = 1인 것을 알고 있으므로 3,7,10을 만들었다

 

[3,7,9]를 보면 3,7,9,10,12,16,19를 만들 수 있는데 단순하게 하면 3 골라보고 7 골라보고 9 골라보고... 3,7 골라보고...

 

복잡한데 이전에 dp[3] = 1, dp[7] = 1, dp[10] = 1이 만들어져 있기 때문에..

 

현재 보는 9에 대하여 21부터 3까지 순회할때 dp[19-9] = dp[10] = 1이므로 dp[19] = 1이다.

 

[3,7]에 9만 넣으면 [3,7,9] = 19가 될 수 있다는 뜻이다.

 

dp[16-9] = dp[7] = 1이므로 dp[16] = 1이다. 역시 [7]에 9를 넣으면 [7,9]가 된다는 뜻이다.

 

dp[12-9] = dp[3] = 1이므로 dp[12] = 1이다. 역시 [3]에 9를 넣으면 [3,9]가 된다는 뜻이다.

 

dp[9-9] = dp[0] = 1이므로 dp[9] = 1이다. 

 

.....

 

--------------------------------------------------------------------------------------------------------------------------------------

 

이렇게 dp에 만들 수 있는 합에 대해 저장해놓는다면?

 

이제 목표는 target = total//2를 만들 수 있는가 아닌가이다

 

target을 못만들더라도, 최대한 target에 가깝게 만들면 좋다. 그래야 두 부분집합 합의 차이가 최소가 되니까

 

i = target부터 0까지 순회해서 dp[i] = 1인 경우를 처음으로 만난다면 그러한 i와 total - i가 

 

합의 차이가 최소가 되는 만들 수 있는 두 부분집합이 된다. 

 

#target에 가장 가깝게 team1을 만들면,
#나머지 하나는 total - team1이므로 합의 차이가 최소가 된다
team1 = 0

for i in range(target,-1,-1):
    
    if dp[i] == 1:

        team1 = i
        break

team2 = total - team1

 

 

 

2. 연습문제1

 

5954번: Dividing the Gold (acmicpc.net)

 

주어진 배열의 합의 차이가 최소가 되도록 두 부분집합으로 분할해야하는데, 그러한 경우의 수까지 구해야한다

 

https://deepdata.tistory.com/951

integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은

 

 

합이 k가 되도록 구성하는 경우의 수를 구하는 방법은 이미 배웠다

 

dp[i] = 배열 v의 원소를 일부 골라 i를 만들 수 있는가?

 

dp[i-w] = 1이면, dp[i] = 1

 

count[i] = 배열 v의 원소를 일부 골라 i를 만드는 방법의 수

 

i를 만들 수 있다면, count[i] += count[i-w]

 

from sys import stdin

n = int(stdin.readline())

v = []

total = 0

for _ in range(n):
    
    w = int(stdin.readline())
    v.append(w)
    total += w

target = total//2

dp = [0]*(target+1)
dp[0] = 1

count = [0]*(target+1)
count[0] = 1
mod = 1000000

for w in v:
    
    for i in range(target,w-1,-1):
        
        if dp[i-w] == 1:
            
            dp[i] = 1
            count[i] += count[i-w]
            count[i] %= mod

team1 = 0

for i in range(target,-1,-1):
    
    if dp[i] == 1:

        team1 = i
        break

team2 = total - team1

print(abs(team1-team2))
print(count[team1])

 

 

3. 연습문제2

 

4384번: 공평하게 팀 나누기 (acmicpc.net)

 

이번엔 합의 차이를 최소로 분할하는건 맞는데, 두 부분집합의 원소 개수 차이가 1 이하여야한다.

 

각 집합의 원소 개수 차이를 알아야하므로, dp 테이블이 각 집합에 들어간 원소의 수도 알고 있어야겠다

 

비슷하게 total을 배열의 모든 원소의 합이라고 하면 target = total//2에 가깝게 맞추는게 제일 좋고

 

두 부분집합의 원소 개수 차이가 1 이하여야하므로,

 

만약 배열의 원소의 개수 n이 짝수이면 n = 6이라고 해보면 

 

3 3

2 4

4 2

5 1

1 5

6 0

0 6

 

이런식으로 되니까 n이 짝수이면 무조건 두 부분집합의 원소의 개수는 n//2로 같아야한다

 

반대로 n이 홀수이면 n = 7이라고 해보면

 

4 3

3 4

5 2

2 5

6 1

1 6...

 

n이 홀수이면 한쪽이 n//2이거나 n//2+1이어야한다

 

 

1) dp[i][j] = 배열 A에서 고른 원소의 개수가 j이고 이들의 원소 합이 i일 수 있는가?

 

그러면 배열의 원소 k에 대하여 dp[i-k][j-1] = 1이면, 현재 k를 더해서 원소 j개로 i를 만들 수 있으므로 dp[i][j] = 1

 

t1 = total//2

dp = [[0]*(n//2+2) for _ in range(t1+1)]
dp[0][0] = 1

for k in w:
    
    for i in range(t1,k-1,-1):
        
        for j in range(n//2+1,0,-1):
            
            if dp[i-k][j-1] == 1:

                dp[i][j] = 1

 

 

이제 i = target = t1부터 0까지 순회해서 dp[i][n//2] 혹은 dp[i][n//2+1]이 가능한지 보면 된다.

 

target에 가까울수록 합의 차이가 최소가 되므로 그러한 i를 발견하기만 하면 끝이다

 

n이 짝수라면 dp[i][n//2]만 보면 될 것이고 n이 홀수라면 dp[i][n//2], dp[i][n//2+1] 2개를 봐야할 것 이다

 

if n % 2 == 0:
    
    m = [n//2]

else:
    
    m = [n//2,n//2+1]

team1 = 0

for i in range(t1,-1,-1):
    
    find = False
    
    for j in m:
        
        if dp[i][j] == 1:
                
            team1 = i
            find = True
            break
            
    if find:
        
        break