냅색 문제는 언제 적용할 것인가?

: 구성요소가 많은데, 그 구성요소들을 이용해 어떤한 조건에 만족하는 값을 구할때 사용된다.
예를 들어서 2원과 3원을 이용해서 10원을 만드려고 할때의 최소 갯수는?

직감적으로 2원 2개와 3월 2개를 이용하면 10원을 만들수 있다.
이 때는 4개를 사용했다.
하지만 2원 5개로도 만들수 있다는 사실! 하지만 최소갯수 이므로 이때는 4개이다.
그런데 이거를 코드로 표현하기에는 좀 번잡하다.
어떻게 해야할지 막막하다.
왜냐하면
10을 가장 큰 3원으로 나누어서 진행할것인가를 생각할 수 있지만,
그렇다면? 3원으로 어디까지 나누어야 할것인가?
나머지가 나올때까지 ?? 그렇다면 이 조건은 말이 안된다.
나머지가 나온다면 3으로 3번 나누는데 나머지 1원은 어떻게 처리할것인가?

---

이와 같이 여러개를 조합해서 최소값이나 최대값을 도출하려고 할때 사용하자.

주의할점

: 최소값을 구하는 것이므로 dp테이블을 크게 설정해놓았다.
하지만 dp[0]값 마저 높은 수라면 갱신이 불가능하다. 따라서
초기화 이후 dp[0]을 0으로 설정해야 한다!

소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;



int main(void) {
	
	int n, m;
	cin >> n >> m;

	vector<int>v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	vector<int>dp(m + 1, 1000);

	dp[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m + 1; j++)
		{
			if(j - v[i] >= 0)
				dp[j] = min(dp[j - v[i]] + 1, dp[j]);
		}
	}

	if (dp[m] == 1000)
		cout << -1;
	else
		cout << dp[m];
}