🙇‍♀️최대점수 구하기(냅색 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다. 

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

▣ 입력예제 1 
5 20
10 5
25 12
15 8
6 3
7 4

▣ 출력예제 1
41

🚀풀이

이 문제는 각 입력값을 한번만 사용해야한다.

동전 교환 문제처럼 중복해서 사용할 수 없으므로 다른 방식을 사용해야하는데 방식이 신기했다.

강의에서 처음에 2차원 배열을 dp로 만들어서 풀었는데 나중에 1차원 배열로 문제를 푸는게 더 이해가 쉬웠다.

void solve()
{
	for (int i = 0; i < n; ++i)
	{
		problem pb = v[i];

		for (int j = m; j >= pb.cost; --j)
		{
			dp[j] = max(dp[j], dp[j - pb.cost] + pb.score);
			res = max(res, dp[j]);
		}
	}

	cout << res;
}

이렇게 코드가 나오는데 j가 m부터 시작해서 내려가는 방식이다.

이렇게 하면 중복해서 사용하지 않고 한번만 사용하는 경우로 만들 수 있다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct problem
{
	int score;
	int cost;
};

int n, m, res = 0;
vector<problem> v;
vector<int> dp;
void setting()
{
	cin >> n >> m;
	v = vector<problem>(n);
	dp = vector<int>(m + 1);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i].score >> v[i].cost;
	}
}

void solve()
{
	for (int i = 0; i < n; ++i)
	{
		problem pb = v[i];

		for (int j = m; j >= pb.cost; --j)
		{
			dp[j] = max(dp[j], dp[j - pb.cost] + pb.score);
			res = max(res, dp[j]);
		}
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}

참고