[C++] 12865: 평범한 배낭

#include <iostream>
#include <algorithm>
using namespace std;
int N, K;

struct Info {
	int weight;
	int value;
};

//N개의 물품들에 대한 정보 저장
Info infos[101];
int dp[101][100001];//보석 N개, 무게 한도 K

int main() {
	scanf("%d%d", &N, &K);

	int w, v;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d", &w, &v);
		infos[i] = { w, v };
	}

	//1개부터 시작해서 N개
	for (int i = 1; i <= N; i++) {
		int nw = infos[i].weight;
		int nv = infos[i].value;
		//가방 한도 1부터 시작해서 K 까지
		for (int j = 1; j <= K; j++) {
			//들어감 -> max(안넣는것, 넣는것)
			if (j >= nw) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nw] + nv);
			else dp[i][j] = dp[i - 1][j];//못 넣는다면, i-1개 들어가 있고 한도가 j인 상황과 같다.
		}
	}
	for (int i = 1; i <= N; i++) {
		//가방 한도 1부터 시작해서 K 까지
		for (int j = 1; j <= K; j++) {
			printf("%d ", dp[i][j]);
		}
		printf("\n");
	}
	printf("%d", dp[N][K]);
}

 

배낭 문제 (dp)