글 읽기 - 평범한 배낭 코드가 어디서 잘못되었는지 알 수 있을까요?

minusie357 4년 전 0

먼저 이 글을 읽어주셔서 감사의 말씀드리겠습니다.

코드 자체는 Dp[i][0]에 무게가 i일 때까지의 가치의 최댓값을 저장하였고, Dp[i][1 ~ N]까지는 해당 최댓값을 도출하는데 사용된 아이템 목록을 1로 표기하였습니다(사용하지 않으면 0).

질문글의 모든 반례 검증 및 임의의 테스트케이스에 대해 코드가 올바른 결과값을 내었지만, 어느 부분에서 틀렸는지 감이 잡히질 않습니다 ㅠㅠ.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#include <chrono>
#include "Utility.h"

chrono::system_clock::time_point Start;
chrono::nanoseconds Time;
#endif



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	pair<int, int> Item[101];
	for (int i = 1; i <= N; ++i)
		cin >> Item[i].first >> Item[i].second;


	static int Dp[100001][101];
	int Max = 0;
	int IdxCopy;	// Dp 복사 위치를 지정하는 인덱스
	int IdxPick;	// 새로 뽑은 아이템 위치를 지정하는 인덱스

	for(int i = 1; i <= K; ++i)
	{
		IdxCopy = i - 1;
		IdxPick = -1;
		for (int j = 1; j <= N; ++j)
		{
			int CurWeight = Item[j].first;
			if (i - CurWeight < 0)
				continue;
			if (Dp[i - CurWeight][j] != 0)
				continue;

			int CurValue = Item[j].second + Dp[i - CurWeight][0];
			if (Max <= CurValue)
			{
				Max = CurValue;
				IdxCopy = i - CurWeight;
				IdxPick = j;
			}
		}

		copy(Dp[IdxCopy], Dp[IdxCopy] + N + 1, Dp[i]); 
		Dp[i][0] = Max;
		if (IdxPick != -1)	Dp[i][IdxPick] = 1;
	}

#ifdef DEBUG
		Print2Dimen(Dp, K + 1, N + 1, true, 1);
#endif // DEBUG

	cout << Dp[K][0] << "\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

평범한 배낭 코드가 어디서 잘못되었는지 알 수 있을까요?

minusie357 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말