8032 : 책 보내기
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
서점에 $N$권의 책이 있습니다. 각 책 $i$의 가격은 $h_i$원이고 페이지 수는 $s_i$페이지입니다. 당신은 최대 $X$원만큼의 예산을 가지고 있습니다. 각 책은 최대 한 권씩만 구매할 수 있다고 할 때, 예산 범위 내에서 구매할 수 있는 책들의 최대 페이지 수 합을 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 1{,}000$
• $1 \le X \le 10^5$
• $1 \le h_i \le 1{,}000$
• $1 \le s_i \le 1{,}000$
[제약 조건]
• $1 \le N \le 1{,}000$
• $1 \le X \le 10^5$
• $1 \le h_i \le 1{,}000$
• $1 \le s_i \le 1{,}000$
입력 설명
첫째 줄에 책의 수 $N$과 최대 예산 $X$가 공백으로 구분되어 주어집니다. ($1 \le N \le 1000$, $1 \le X \le 10^5$)
둘째 줄에 각 책의 가격 $h_1, h_2, \ldots, h_N$이 공백으로 구분되어 주어집니다. ($1 \le h_i \le 1000$)
셋째 줄에 각 책의 페이지 수 $s_1, s_2, \ldots, s_N$이 공백으로 구분되어 주어집니다. ($1 \le s_i \le 1000$)
둘째 줄에 각 책의 가격 $h_1, h_2, \ldots, h_N$이 공백으로 구분되어 주어집니다. ($1 \le h_i \le 1000$)
셋째 줄에 각 책의 페이지 수 $s_1, s_2, \ldots, s_N$이 공백으로 구분되어 주어집니다. ($1 \le s_i \le 1000$)
출력 설명
구매할 수 있는 책들의 최대 페이지 수의 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 10
4 8 5 3
5 12 8 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
13도움
전형적인 0-1 배낭 문제(0-1 Knapsack Problem)입니다. 1차원 DP 테이블 $dp[j]$ ($0 \le j \le X$)를 사용해 공간 복잡도를 최적화할 수 있습니다. 각 책 $i$를 하나씩 선택하면서, 예산 $j$를 큰 값($X$)부터 책 가격 $h_i$까지 역순으로 돌며 $dp[j] = \max(dp[j], dp[j-h_i] + s_i)$로 업데이트하면 중복 구매 없이 최대 페이지를 계산할 수 있습니다.