BOJ 12865: 평범한 배낭 작성일 2020-02-18 https://www.acmicpc.net/problem/12865 2월동안 187문제 풀기(지난달 누적 87개) (36/187) 냅색 문제는 배낭에 넣을때 큰 무게부터 넣어야 한다. 그래야 두번 넣지 않게 된다. 1234567891011121314151617181920#include <bits/stdc++.h> using namespace std; int N, K, W, V; int main() { ios::sync_with_stdio(false); cin >> N >> K; vector<int> pack(K+1); for(int i = 0; i < N; i++) { cin >> W >> V; for(int k = K; k >= W; k--) pack[k] = max(pack[k-W] + V, pack[k]); } int ans = 0; for(int k = 0; k <= K; k++) ans = max(ans, pack[k]); cout << ans; }