[n1535] 안녕 in python (배낭문제)

1535번 안녕 문제는 

브루트포스 알고리즘, 배낭 문제에 해당한다.

 

(처음에 내가 생각했던 풀이)

itertools 라이브러리 combination을 이용하여

먼저 경우의 수를 찾고

그 수들 중에 조건을 만족하면서 값이 최대인 수를

출력하게끔 했다.

 

answer에 아무 숫자가 들어가있지 않다면

조건에 해당하는 경우가 하나도 없다는 것을 의미한다.

그래서 0을 출력하게끔 처리해야

valueError가 발생하지 않는다.

 

제한 시간은 2초인데

실행 시간이 1.2초 나와서..

내 코드보다 더 효율적인 코드를 찾아 떠나보았다.

import itertools

person = int(input())
loss = list(map(int, input().split()))
smile = list(map(int, input().split()))

joon_health = 100
joon_smile = 0

answer=set()

for i in range(person, 0, -1):
    loss_combi = list(itertools.combinations(loss, i))
    smile_combi = list(itertools.combinations(smile, i))
    for j in range(len(loss_combi)):
        now_sum = sum(loss_combi[j])
        if now_sum > 99:
            continue
        # 기쁨
        answer.add(sum(smile_combi[j]))
if len(answer)>0:
    print(max(answer))
else:
    print(0)

 

---

[ 인터넷 참고 코드 ]

배낭문제 - > dp 이용

dp[0]~dp[99] : 총 100, 손실 기준 (최소0~최대100)

 

minus=[1,21,79]

smile=[20,30,25]

 

1. minus=1, smile=20일 때

dp[99:0] : 99~1까지 for문 돌린다.

dp[99] = max(dp[99],dp[99-minus]+smile)

> 0 vs 20 > 20

....

dp[1]=max(dp[1],dp[1-minus]+smile)

> 0 vs 20 > 20

---

2. minus=21, smile=30일 때

dp[99:20] : 99~21까지 for문 돌린다.

dp[99] = max(dp[99],dp[99-minus]+smile)

> 20 vs 20+30=50 > 50

....

dp[21]=max(dp[21],dp[21-minus]+smile)

> 20 vs 30 > 30

---

3. minus=79, smile=25일 때

dp[99:78] : 99~79까지 for문 돌린다.

dp[99] = max(dp[99],dp[99-minus]+smile)

> 50 vs 20 + 25 = 45 > 50

....

dp[79]=max(dp[79],dp[79-minus]+smile)

> 50v s 25 > 50

 

 

20 .. 99

19 .. 98

18 .. 97

17 .. 96

16 .. 95

15 .. 94

14 .. 93

.....

0 .. 79

 

0	1	....	21	...	79	....	99
0	20	20	20	20	20	20	20
0	20	20	30	50	50	50	50
0	20	20	30	50	50	50	50

 

n=int(input())
minus=list(map(int,input().split()))
smile=list(map(int,input().split()))
dp=[0]*100
for idx,d in enumerate(minus):
	for i in range(99,d-1,-1):
		dp[i]=max(dp[i],dp[i-d]+smile[idx])
print(dp[99])

 

 

배낭 문제 유형이 아직 익숙치 않아서

자료를 찾아보다 이해가 쏙쏙 되는 게시글 링크 첨부

https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C