Ciao Ragazzi sto provando a risolvere il problema chiamato “Fibonacci Colonies” ho fatto un programma che per quanto riguarda i file input me li risolve, però quando lo carico sulla piattaforma mi dà soltanto 10/100, però non riesco a capire perché alcune subtask escono sbagliate, potete aiutarmi a capire il problema del programma??
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <math.h>
// constraints
#define MAXN 100000
#define MAX_FIBONACCI 25
/*
input data
*/
int T; // Number of days
int N; // Number of offers on the specific day
int K; // Max number of ants that can be sold that day
int i, j; // Index for iterations
int formichePerGrado[MAX_FIBONACCI];
int A[MAXN]; // Degree of colony i
int B[MAXN]; // Price of colony i
int numeroFormiche(int n) {
formichePerGrado[0] = 1;
formichePerGrado[1] = 1;
for (int k = 2; k < n; k++)
formichePerGrado[k] = formichePerGrado[k - 1] + formichePerGrado[k - 2];
return formichePerGrado[n - 1];
}
int max(int a, int b) {
return (a > b) ? a : b;
}
bool check1(int d) {
if (d >= 1 && d <= 100000)
return true;
return false;
}
bool check2(int e) {
if (e >= 1 && e <= pow(10, 9)) {
return true;
}
return false;
}
int unboudedKnapSack(int numeroOfferte, int numeroMassimoFormiche, const int colonneOfferte[], int prezzoColonne[]) {
if (numeroOfferte == 0 || numeroMassimoFormiche == 0)
return 0;
int pesoMax = numeroMassimoFormiche;
int tabella[pesoMax + 1];
for (int z = 0; z <= pesoMax; z++) { //righe di offerte, dove offerta = n. formiche x prezzo
tabella[z] = 0;
}
for (int z = 0; z <= numeroOfferte; z++) {
if (colonneOfferte[z] < MAX_FIBONACCI && check1(numeroOfferte) && check1(numeroMassimoFormiche) &&
check2(formichePerGrado[colonneOfferte[z]])) {
//corrisponde alle colonnne, se ho 5 formiche indicePeso = 5
int indicePeso = formichePerGrado[colonneOfferte[z]];
for (int k = 0; k <= pesoMax; k++) {
if (k >= indicePeso) {
//valore da considerare quando torno indietro (capienza dello zaino di prima)
int valoreShiftatoDiagonale = tabella[k - indicePeso];
//valore che c'e' adesso
int valorePrecedente = tabella[k];
//valore massimo tra valore item + valore shiftato e valore che c'e' adesso
tabella[k] = max(valorePrecedente, prezzoColonne[z] + valoreShiftatoDiagonale);
}
}
}
}
return tabella[pesoMax];
}
/**
* @brief Calculate maxiumum reveneu using Unbounded Knapsack Problem (UKP)
*
* @param Capacity Max knapsack capacity
* @param N Number of possibile elements
* @param weight Weight of each element
* @param values Value of each element
* @return long Max possibile reveneu
*/
int main() {
assert(1 == scanf("%d", &T)); //numero dei giorni
//calcolo numero formiche
numeroFormiche(MAX_FIBONACCI);
// Cycle each day
if (check1(T)) {
for (i = 0; i < T; i++) {
// Read first two values
assert(2 == scanf("%d %d", &N, &K)); //N numero di offerte K numero massimo di formiche da vendere
// Fill A and B with values
for (j = 0; j < N; j++) {
assert(2 == scanf("%d %d", &A[j], &B[j])); //A colonna offerta B prezzo per colonna
}
printf("%d\n", unboudedKnapSack(N, K, A, B));
}
}
return 0;
}