낙곡 동태 기획 훈련 총결산: 즐거운 금명 시리즈

몇 가지 물품을 선정한 다음에 그 안에서 특정 물품을 골라 가치가 가장 큰 문제를 만들어야 한다.이런 김명 문제는 두 가지가 있다.

유형 1

하나는 모든 아이템을 한 번씩 선택할 수 있는데 선택하면 없어진다. 이때 dp[i][j]는 전 i종을 선택할 수 있고 선택한 후에 j원을 써야 한다는 뜻이다.이때 dp[i][j]의 구분은 d[i][j]={방안1: 마침 i종을 사지 않는다. 이때 dp[i-1][j]방안2: i종을 사야 한다. 그리고 i종은 1종만 사고 나머지는 i-1종을 사야 한다. 그리고 가장 가치가 큰 것은 dp[i-1][j-1*list[i].v]+listi].v*[listi].w]이다.

유형 2

모든 물품은 임의로 여러 번 선택할 수 있다. 이때 dp[i][j]는 전 i종을 선택할 수 있고 선택한 후에 j원을 적당히 쓴다.(즉 앞에서 정의한 것과 같다) 이때 dp[i][j]의 구분은 dp[i][j]={방안1: 마침 i종을 사지 않는다. 이때는 dp[i-1][j]방안2: i종을 사야 하고 i종은 적어도 1개를 사야 한다. 나머지 돈은 i종을 살 수 있고 가치가 가장 큰 것은 dp[i][j-1*listi].v]+list[i].v*listi].w}이다. 이때 코드는 다음과 같다.

int main() {
	int dp[30001];
	int N, m;
	cin >> N >> m;
	obj list[26];
	for (int i = 1; i <= m; i++) {
		cin >> list[i].v >> list[i].w;
	}
	dp[0] = 0;
	memset(dp, 0, sizeof(dp));
	int tempmax=0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= m; j++) {
			int index = i - list[j].v;
			if (index>= 0) {
				dp[i]= max(dp[index] + list[j].v*list[j].w, dp[i]);
			}
		}
	}
	cout << dp[N];
	return 0;
}

나머지 사고

동적 기획의 표 찾기 방법 dp[i][j]에서 i와 j가 서로 다른 문제에서 주의해야 할 점이 있음을 알 수 있다. 본 문제를 예로 들면

j에 대해 j원을 마침 다 썼다는 것을 주의해야 하기 때문에 정상적으로 i행의 원소를 두루 겪어야 한다.

i에 대해 남은 돈으로 i종을 살 수 있는지 i-1종을 살 수 있는지 주의해야 한다