글 읽기 - 평범한 배낭) 백트래킹 + memo 방식 질문드립니다

ohyeaha 2년 전 0

안녕하세요, 평범한 배낭문제 백트래킹 + memo로 접근 해보았습니다.

예제와 찾은 반례들은 정상적으로 나오는데, 제출하면 즉시 '틀렸습니다' 가 출력됩니다.

어디가 잘못 되었는지, 접근이 아예 틀린건지 조언을 주시면 감사하겠습니다.

#include <iostream>

using namespace std;

int N, K;
int W[101], V[101];
bool selected[101];
int memo[10000001];

int checknode(int index, int weight, int value, int level) {
	if (memo[weight] != 0) return memo[weight];

	for (int i = index; i < N; ++i) {
		if (selected[i]) continue;

		int nextWeight = weight + W[i];
		if (nextWeight > K)	continue;
		int nextValue = value + V[i];

		selected[i] = true;
		memo[weight] = max(memo[weight], nextValue);
		memo[weight] = max(memo[weight],
			checknode(i, nextWeight, nextValue, level + 1));
		selected[i] = false;
	}
	return memo[weight];
}

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

	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		cin >> W[i] >> V[i];
	}
	cout << checknode(0, 0, 0, 0);
	return 0;
}

/*
4 7
6 13
4 8
3 6
5 12
ans: 14

10 999
46 306
60 311
33 724
18 342
57 431
49 288
12 686
89 389
82 889
16 289
ans: 4655

1 2
1 3
ans: 3

3 5
4 2
3 4
1 5
ans: 9

3 10
1 1
9 2
10 1
ans: 3
/*

ohyeaha 2년 전 0

memo의 차원과 가지치기 조건이 잘못된 방식이었습니다.

memo[10000001] -> memo[101][100001]

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

문제

문제

출처

ICPC

평범한 배낭) 백트래킹 + memo 방식 질문드립니다

ohyeaha 2년 전 0

ohyeaha 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말