201. 평범한 배낭
1) 어떤 전략(알고리즘)으로 해결?
DP DP DP
2) 코딩 설명
<내 풀이>
import sys
# 최대 K만큼의 무게만을 넣을 수 있는 배낭만
n,k = map(int, sys.stdin.readline().rstrip().split())
# N : 첫 줄에 물품의 수
# K : 준서가 버틸 수 있는 무게
wvsave = []
# W, V : 무게, 즐거움
for i in range(n) :
w,v = map(int, sys.stdin.readline().rstrip().split())
wvsave.append((w,v))
bag = [0 for _ in range(k+1)]
for b in range(n) :
w,v = wvsave[b]
for m in range(k, w-1, -1) : # 주석 참고
bag[m] = max(bag[m], bag[m-w]+v)
print(bag[-1])
# 처음에는 인덱스 0 부터 끝까지로 했는데, 이러면 누적됨
# (ex) 아래같이 input 들어오고 0->3 검사하면
# (0, 5, 10, 15) 일케 쌓임
# 3 5
# 4 2
# 3 4
# 1 5
# 따라서 3->0 으로 검사하면 (0, 5, 5, 5) 로 쌓임<내 틀렸던 풀이, 문제점>
- 아래는 한 물건을 여러개 뽑을 수 있다고 가정하는 코드, 그러나 이 문제는 단 한번씩만 담기기 가능
- 순서대로 물건을 담아주면 물건이 계속 누적되는 문제 발생, 여기서는 물건은 단 한개씩이니 이렇게 되면 안돼용
import sys
# 최대 K만큼의 무게만을 넣을 수 있는 배낭만
n,k = map(int, sys.stdin.readline().rstrip().split())
# N : 첫 줄에 물품의 수
# K : 준서가 버틸 수 있는 무게
wvsave = []
# W, V : 무게, 즐거움
for i in range(n) :
w,v = map(int, sys.stdin.readline().rstrip().split())
wvsave.append((w,v))
bag = [0 for _ in range(k+1)]
for b in range(n) :
w,v = wvsave.pop()
for k in range(w,k+1) :
bag[k] = max(bag[k-w]+v, bag[k])
print(bag[-1])
80%에서 틀리는 코드 - 코너케이스 고려안하고 range를 (1,n)으로 함
그렇게 하면 n이 1 인 경우에는 에러가 나게 되지
import sys
# 최대 K만큼의 무게만을 넣을 수 있는 배낭만
n,k = map(int, sys.stdin.readline().rstrip().split())
# N : 첫 줄에 물품의 수
# K : 준서가 버틸 수 있는 무게
wvsave = []
# W, V : 무게, 즐거움
for i in range(n) :
w,v = map(int, sys.stdin.readline().rstrip().split())
wvsave.append((w,v))
bag = [0 for _ in range(k+1)]
wvsave.sort(reverse=True)
for b in range(1,n) :
w,v = wvsave[b]
for m in range(k, w-1, -1) :
bag[m] = max(bag[m], bag[m-w]+v)
# print()
# print(bag)
print(bag[-1])
<반성 점>
<배운 점>
1) 어떤 전략(알고리즘)으로 해결?
2) 코딩 설명
<내 풀이>
<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>
출처 : 출처
