백준 1535 - 안녕

백준 1535 - 안녕

https://www.acmicpc.net/problem/1535

★ 풀이

전형적인 knapsack(배낭) 문제. 풀이방법은 크게 두 가지(top-down, bottom-up) 로 나누어지며, 둘 다 해본 결과.. 이런 문제 유형은 종만북에서도 기재되어 있는 top-down 방식이 내게 더 편한 것 같다.

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int need[],volume[],d[][]; static int n; public static void main(String[] args) throws IOException { n = Integer.parseInt(br.readLine()); need = new int[21]; volume = new int[101]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { volume[i] = Integer.parseInt(st.nextToken()); } st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { need[i] = Integer.parseInt(st.nextToken()); } d = new int[101][21]; System.out.println(pack(100, 0)); } static int pack(int capacity, int item) { if (item == n) return 0; if (d[capacity][item] == 0) { d[capacity][item] = pack(capacity, item + 1); if (capacity > volume[item]) { d[capacity][item] = Math.max(d[capacity][item], pack(capacity - volume[item], item + 1) + need[item]); } } return d[capacity][item]; } }

from http://sweet-smell.tistory.com/56 by ccl(A) rewrite - 2021-09-26 21:26:53