Problemas
무게와 가격이 주어진 n개의 물건이 있다. 이 물건을 어떤 가방에 들어 있는 물건의 가격의 합을 최대화 하려고 한다.
허나 이 가방은 집어넣을 수 있는 물건의 합이 제한이 있기 때문에 전부 넣지 못하는 경우도 발생하므로 넣을 물건을 잘 선택해야 한다.
일반적인 경우엔 이 문제는 NP-complete문제로 알려져 있기에 효율적으로 풀기는 어렵다고 알려져 있다.
Dynamic Programming solution이 있다고 하여도 이 문제는 NP-complete가 확실하다.)
허나 어떤 특별한 제약 조건이 있을 경우에는 효율적인 해법이 있을 경우도 생긴다.
이번 문제에서는, 모든 물건의 무게가 피보나치수열의 숫자인 경우의 문제를 풀어보려 한다.
첫 번째와 두 번째의 피보나치수열의 숫자는 1과 2이며,
1, 2, 3, 5, 8, 13과 같이 각 각의 수열에 위치한 숫자들은 앞의 두 개의 숫자의 합으로 만들어진다.
가방에 담을 수 있는 물건의 최대 무게와 각 물건의 무게와 가격이 주어졌을 때
가방에 넣을 수 있는 물건들의 가격의 합이 최대가 얼마인지 알아보는 프로그램을 작성하라.
Entrada
입력은 여러 개의 테스트 케이스로 이루어지며
입력의 첫 번째에는 테스트 케이스의 개수 T(T≤20)가 입력된다. 테스트 케이스의 첫 번째 줄에는 가방에 담을 수 있는 물건의 최대 합 C가 입력된다.(1≤C≤1016)
두 번째 줄에는 물건의 개수 N(1≤N≤50)이 입력된다. 세 번째 줄부터 N개의 줄에는 각 물건의 무게와 가격이 주어진다. 무게와 가격은 1016이하의 양의 정수이다.
Salida
테스트 케이스에 대하여 물건을 담았을 때 얻을 수 있는 최대 가격의 합을 출력한다.
Ejemplo
2
15
3
5 555
8 195
13 651
94
6
55 1562
5 814
55 1962
8 996
2 716
34 1792
750
4568
Debes iniciar sesión para escribir código.