백준 7579번 링크 Knapsack problem Optimization version NP hard 문제이다. Optimization version의 정의는 다음과 같다. Input: Positive integers $$W, w{1}, ... , w{n}$$ and $$v{1}, ... , v{n}$$ Output: A subset S $$\subset$$ {1, ... , n} that maximizes $$\Sigma{i\in S}v{i}$$ subject to $$\Sigma{i\in S}w{i} \le W$$ 쉽게 말하면 n개의 배낭이 있고, 각 배낭은 가격과 가치가 있다. 한정된 돈으로 최대한의 가치를 얻는 방법을 묻는 문제다. weight와 value라고 표현하는 게 개인적으로 편한 것 같다. Deicision version 이 문제가 NP hard인 것을