글 읽기 - 피보나치 냅색 증명하실 수 있는 수학깡패분 계신가요 ㅠㅠ?

shjgkwo 9년 전 0

음, 이걸 뭐라고 설명해야하지

동일한 숫자내에서는 일단 큰것부터 연속적인것을 선택하는게 좋고 따라서, 연속적인 게 아니면 백트랙

그 무게를 더 이상 뺄 수 없거나, 그 무게가 없으면, 뺄 수 있는 다음 무게를 찾아서 빼주고

나머지는 연속적인 합에서 허용되는 범위라면, 무조건 그걸 가져가고 백트랙

대충 이런 내용인데요, 일반적인 경우라면 O(2^50) 으로 시간초과가 나야 정상이지만,

시간초과가 안나네요? 피보나치 성질때문에 그런것 같은데...

증명해주실 수 있는 수학깡패분 계신가요 ㅠㅠ?

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct bung {
	ll w;
	ll c;
}o[52];
int n;
ll maxw;
ll maxc = 0;
ll hapw[52], hapc[52];
bool fsort(bung a, bung b) {
	if (a.w != b.w) return a.w > b.w;
	else return a.c > b.c;
}
void solv(ll c, ll w, int i, bool sw) {
	if (maxc < c) maxc = c;
	if (w >= hapw[i]) {
		ll tmp;
		tmp = c + hapc[i];
		if (maxc < tmp) maxc = tmp;
		return;
	}
	if (sw && o[i].w == o[i-1].w) {
		solv(c, w, i + 1, sw);
		return;
	}
	if (w - o[i].w >= 0) solv(c + o[i].c, w - o[i].w, i + 1, false);
	solv(c, w, i + 1, true);
}
void _in() {
	int i;
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%lld %lld", &o[i].w, &o[i].c);
	scanf("%lld", &maxw);
	std::sort(o, o + n, fsort);
	hapw[n - 1] = o[n - 1].w;
	hapc[n - 1] = o[n - 1].c;
	for (i = n-2; i >= 0; i--) {
		hapw[i] = hapw[i + 1] + o[i].w;
		hapc[i] = hapc[i + 1] + o[i].c;
	}
}
int main() {
	_in();
	solv(0, maxw, 0, 0);
	printf("%lld\n", maxc);
	return 0;
}

baekjoon 9년 전 1

Zeckendorf Representation: http://mathworld.wolfram.com/ZeckendorfRepresentat...

아마 이것때문에 그렇지 않을까요?

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

문제

문제

출처

ICPC

피보나치 냅색 증명하실 수 있는 수학깡패분 계신가요 ㅠㅠ?

shjgkwo 9년 전 0

baekjoon 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말