sto seguendo il percorso di algobadge sulla programmazione dinamica e pranzo dalla nonna è uno dei problemi che propone. Ho compreso bene o male come funziona il problema del knapsack ma non riesco ad applicarlo in nessun modo a questo specifico problema.
di seguito c’è il codice che ho scritto fino ad ora:
#include <stdio.h>
#include <assert.h>
#include
using namespace std;
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
int tab[100][1000];
int mangia(int N, int K, int P, int ind) {
if (ind >= N)
return 0;
if (K <= 0)
return 0;
else if (K > 0 && ind >= N)
return -10000000000;
return max(P[ind] + mangia(N, K - P[ind], P, ind + 1), mangia(N, K, P, ind + 1));
}
int P[MAXN];
int main() {
int N, K;
cin >> N >> K;
for (int i = 0; i < N; i++)
cin >> P[i];
cout<<mangia(N, K, P, 0);
return 0;
}
la logica che ho provato a seguire è la seguente: massimizza i piatti finchè non si giunge ad una situazione dove k<=0, in quel caso si ritorna 0, se si dovesse giungere alla fine dell array anche si ritorna 0 e nel caso arrivati alla fine dell’ array la somma dovesse essere ancora maggiore di k (k > 0) il programma ritorna un numero che dovrebbe rappresentare meno infinito in modo tale da non farlo prendere in considerazione dal max(…). mi rendo conto che questa soluzione non funziona e ho una vaga idea del perchè, ma mi chiedevo se qualcuno potesse riportarmi sulla retta via con qualche dritta.
Grazie