트럭 적재 최적화
골드 V의견: 0
도매상 준호는 트럭 한 대에 최대 적재량 \(W\) 만큼의 상자를 실으려 한다. 가게에는 \(N\) 종류의 상품이 있고, \(i\) 번째 상품 한 개의 무게는 \(w_i\), 이익은 \(v_i\) 이며 재고는 \(c_i\) 개이다.
같은 종류의 상품을 재고 수 \(c_i\) 개까지 여러 개 실을 수 있다. 실은 상품들의 무게 합이 \(W\) 를 넘지 않도록 하면서 이익의 합을 최대로 하려 한다.
얻을 수 있는 이익 합의 최댓값을 구하여라.
- \(1 \le N \le 50\)
- \(1 \le W \le 20{,}000\)
- \(1 \le w_i \le W\)
- \(1 \le v_i \le 1{,}000\)
- \(1 \le c_i \le 100\)
첫째 줄에 상품 종류 수 \(N\) 과 최대 적재량 \(W\) 가 주어진다.
이어지는 \(N\) 개의 줄에 각각 \(w_i\), \(v_i\), \(c_i\) 가 공백으로 구분되어 주어진다.
실을 수 있는 이익 합의 최댓값을 한 줄에 출력한다.
2 10
2 3 4
3 4 214무게 2짜리를 4개, 무게 3짜리는 못 넣으면 무게 8 이익 12가 되지만 다른 조합이 더 클 수 있다.
2 5
5 100 1
5 100 1100적재량 5에는 무게 5 상품 하나만 들어가므로 이익은 100이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
트럭 적재 최적화
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
트럭 적재 최적화