7312 : 재귀 배낭
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
0/1 배낭 문제: $N$개의 물건이 있으며, 각각 무게와 가치를 가집니다. 배낭의 최대 무게 $W$ 이하로 물건을 담을 때 가치의 최댓값을 구하십시오.
탑다운 재귀 + 메모이제이션으로 구현합니다.
점화식: $\text{dp}(i, w) = \max(\text{dp}(i-1, w),\ \text{dp}(i-1, w - w_i) + v_i)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
탑다운 재귀 + 메모이제이션으로 구현합니다.
점화식: $\text{dp}(i, w) = \max(\text{dp}(i-1, w),\ \text{dp}(i-1, w - w_i) + v_i)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 물건의 개수 $N$과 배낭의 최대 무게 $W$가 주어집니다. ($1 \le N \le 100$, $1 \le W \le 100{,}000$)
둘째 줄부터 $N$개의 줄에 각 물건의 무게와 가치가 주어집니다.
둘째 줄부터 $N$개의 줄에 각 물건의 무게와 가치가 주어집니다.
출력 설명
배낭에 담을 수 있는 물건들의 가치의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 7
2 3
3 4
4 5
5 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
9도움
memo = {}; def dp(i, w): if i==0 or w==0: return 0; if (i,w) in memo: return memo[(i,w)]; if weight[i]>w: result=dp(i-1,w); else: result=max(dp(i-1,w), dp(i-1,w-weight[i])+value[i]); memo[(i,w)]=result; return result