백준 12865. 평범한 배낭

문제 링크

난이도	정답률(_%)
Gold 5	37.501%

설계

• 준서가 버틸 수 있는 무게 K (<= 100,000)
• 물품의 수 N (<= 100)
• 어떤 무게에서 가질 수 있는 최대 가치는 물품 한개이거나, 어떤 물품과 더해졌을 때 가장 최대 가치를 가질 수 있다. 따라서 각 무게에서 가질 수 있는 최대 가치를 계속 비교하면서 갱신한다.

시간 복잡도

• N개의 물품에 대해 최대 K번까지 검사
• O(N*K), 최대 10,000,000

공간 복잡도

• 각 무게별 가치를 저장할 int 형 배열, 길이 100001
• 각 물품을 저장할 Product형 배열, 길이 101

풀이

• 각 물품에 대해 최대 무게부터 자신의 무게까지 아래 내용을 반복한다.
  • 가방의 현재 무게의 가치와 (현재 무게 - 자신의 무게)무게의 가치 + 자신의 가치를 비교해 더 큰 값을 저장한다.
• 최대 무게에서의 가치를 출력한다.

결과

메모리	실행 시간
14624KB	132ms

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] information = br.readLine().split(" ");
        int productNumber = Integer.parseInt(information[0]);
        int maxWeight = Integer.parseInt(information[1]);

        Product[] products = new Product[101];
        int[] bags = new int[100001];

        for (int i = 0; i < productNumber; i++) {
            String[] product = br.readLine().split(" ");
            products[i] = new Product(product);
        }

        for (int i = 0; i < productNumber; i++) {
            for (int j = maxWeight; j >= products[i].weight; j--) {
                bags[j] = Math.max(bags[j], bags[j - products[i].weight] + products[i].value);
            }
        }

        bw.write(Integer.toString(bags[maxWeight]));

        bw.flush();
        bw.close();
    }
}

class Product {
    int weight;
    int value;

    public Product(String[] productInformation) {
        this.weight = Integer.parseInt(productInformation[0]);
        this.value = Integer.parseInt(productInformation[1]);
    }
}