static class Cargo {

// 가치($)

int price;

// 무게(kg)

int weight;

public Cargo(int price, int weight) {

this.price = price;

this.weight = weight;

}

}

public static int zeroOneKnapsack(List<Cargo> cargos) {

// 용량

int capacity = 15;

// 짐 개수 x 배낭 용량, 2차원 배열 선언

int[][] pack = new int[cargos.size() + 1][capacity + 1];

for (int i = 0; i <= cargos.size(); i++) {

// 배낭 용량을 점점 늘려가며 순회

for (int c = 0; c <= capacity; c++) {

if (i == 0 || c == 0) {

pack[i][c] = 0;

} else if (cargos.get(i - 1).weight <= c) {

// 현재 짐 무게가 배낭 용량 이내인 경우 최대 가격 계산

pack[i][c] = Math.max(

// 현재 짐 가격 + 이전 짐의 현재 짐 무게를 뺀 용량의 가격

cargos.get(i - 1).price + pack[i - 1][c - cargos.get(i - 1).weight],

pack[i - 1][c]

);

} else {

// 용량을 넘어선 경우 이전 짐의 가격을 그대로 이관

pack[i][c] = pack[i - 1][c];

}

}

}

return pack[cargos.size()][capacity];

}

public static void main(String[] args) {

List<Cargo> cargos = new ArrayList<>();

cargos.add(new Cargo(4, 12));

cargos.add(new Cargo(2, 1));

cargos.add(new Cargo(10, 4));

cargos.add(new Cargo(1, 1));

cargos.add(new Cargo(2, 2));

int result = zeroOneKnapsack(cargos); // 15

System.out.println(result);

}