백준 12865, 평범한 배낭

문제

https://www.acmicpc.net/problem/12865

풀이

나눌 수 없는 배낭 문제의 아주 기초적인 문제이다. 처음에는 이걸 어떻게 구현하나 생각했는데 첫번째 index에는 넣을 수 있는 물건의 종류, 두번째 index에는 무게로 구현하면 임의의 i에 대해서 dp[i][?] 에서는 i를 넣을 것만 고려하면 되기때문에 같은 물건을 중복해서 넣는 문제가 해결되고 이를 통해 dp를 진행하면 쉽게 풀린다.

다만 처음 쓰는 알고리즘이다 보니 틀을 익히지는 못하고 구현만 했다. 이 문제를 또 봐도 쉽게 풀 수 있도록 틀을 익히자.

실수

• 배낭 알고리즘 틀을 익히기
• 시간이 좀 오래걸림 (45분)
• 구현하는데 시간이 좀 걸림 (잔실수가 있었음)

풀이

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<utility>

#define M 1000000

using namespace std;

int n, w;
vector<vector<int>> dp(110, vector<int>(110000, 0));
vector<pair<int, int>> thing;

int main() {

	scanf("%d %d", &n, &w);

	for (int i = 0; i < n; i++) {

		int weight, value;

		scanf(" %d %d", &weight, &value);

		thing.push_back(make_pair(weight, value));

	}

	for (int i = 0; i < n; i++) {

		for (int j = 0; j <= w; j++) {

			if (i == 0)
				dp[i][thing[i].first] = thing[i].second;

			else if (0 <= j - thing[i].first)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - thing[i].first] + thing[i].second);

			else
				dp[i][j] = dp[i - 1][j];

		}

	}

	int result = 0;

	for (int i = 0; i <= w; i++) {

		result = max(result, dp[n - 1][i]);

	}

	printf("%d", result);

	return 0;



}