8036 : 표준 배낭 문제
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
배낭의 최대 허용 크기 $S$와 $N$개의 물건이 주어집니다. 각 물건 $i$는 크기 $v_i$와 가치 $c_i$를 가집니다. 배낭의 허용 크기를 초과하지 않으면서 배낭에 담을 수 있는 물건들의 가치 합의 최대값을 구하는 프로그램을 작성하시오. 단, 각 물건은 단 하나씩만 존재합니다.
[제약 조건]
• $1 \le S \le 2{,}000$ (배낭 용량)
• $1 \le N \le 2{,}000$ (물건 개수)
• $1 \le v_i, c_i \le 2{,}000$
[제약 조건]
• $1 \le S \le 2{,}000$ (배낭 용량)
• $1 \le N \le 2{,}000$ (물건 개수)
• $1 \le v_i, c_i \le 2{,}000$
입력 설명
첫째 줄에 배낭의 용량 $S$와 물건의 개수 $N$이 공백으로 구분되어 주어집니다. ($1 \le S \le 2000$, $1 \le N \le 2000$)
다음 $N$개의 줄에 각 물건의 크기 $v_i$와 가치 $c_i$가 공백으로 구분되어 주어집니다. ($1 \le v_i, c_i \le 2000$)
다음 $N$개의 줄에 각 물건의 크기 $v_i$와 가치 $c_i$가 공백으로 구분되어 주어집니다. ($1 \le v_i, c_i \le 2000$)
출력 설명
담을 수 있는 물건들의 최대 가치 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1 8
2 4
3 0
2 5
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
13도움
가장 기본적인 0-1 배낭 문제(0-1 Knapsack Problem)입니다. 1차원 DP 테이블 $dp[j]$ ($0 \le j \le S$)를 0으로 초기화한 뒤, 각 물건의 크기 $v$와 가치 $c$에 대해 용량 $j$를 큰 값($S$)부터 $v$까지 역순으로 순회하며 $dp[j] = \max(dp[j], dp[j-v] + c)$로 갱신하면 됩니다. 시간 복잡도는 $O(N \times S)$ 입니다.