Buongiorno, sono alle prime armi con la programmazione dinamica e sto cercando di risolvere il problema “Pranzo dalla nonna”. Mi hanno consigliato di guardare il problema “Knapsack” e ho scritto questa soluzione, cosa sto sbagliando?
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
using namespace std;
vector <int> P;
int max (int b, int a)
{
if (a>b)
return a;
else
return b;
}
int mangia (int N, int K, bool uguale)
{
if (N==1)
return P[0];
else if (uguale==true)
return K;
else
{
sort (P.begin(), P.end());
bool primo=false;
if (P[0]>K)
return P[0];
for (int i=0; i<N; i++)
{
if (P[i]>K&&primo==false)
primo=true;
else if (P[i]>K&&primo==true)
{
i--;
N--;
P.erase(P.begin()+i);
}
}
int tab[N+1][K+1];
for (int n=0; n<=N; n++)
{
for (int k=0; k<=K; k++)
{
if (n==0||k==0)
tab[n][k]=0;
else if (k==1&&n!=0)
tab[n][k]=P[0];
else if (tab[n][k-1]>=k)
tab[n][k]=tab[n][k-1];
else if (tab[n-1][k]>=k)
tab[n][k]=tab[n-1][k];
else
tab[n][k]=max (P[n-1]+tab[n-1][k-P[n-1]], tab[n-1][k]);
}
}
return tab[N][K];
}
}
int main ()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
bool uguale=false;
int N, K, x;
cin>>N>>K;
for(int i=0; i<N; i++)
{
cin>>x;
P.push_back(x);
if (K==x)
uguale=true;
}
cout<<mangia (N, K, uguale);
return 0;
}
Ciao, l’approccio del tuo algoritmo tende a massimizzare l’insieme delle portate di peso superiore a K mentre il problema chiede di trovare il peso minimo superiore a K.
Con questo input:
4 12
5 13 5 5
il tuo algoritmo restituisce 15, mentre il risultato corretto è 13.
Grazie, ho provato a lavorare a questo caso specifico che non funzionava e ho migliorato un po’ il codice ottenendo 30/100. C’è qualche problema con le variabili, va fuori tempo o cosa?
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
using namespace std;
vector <int> P;
int max (int b, int a)
{
if (a>b)
return a;
else
return b;
}
int min (int b, int a)
{
if (a<b)
return a;
else
return b;
}
int mangia (int N, int K, bool uguale)
{
if (N==1)
return P[0];
else if (uguale==true)
return K;
else
{
sort (P.begin(), P.end());
bool primo=false;
if (P[0]>K)
return P[0];
for (int i=0; i<N; i++)
{
if (P[i]>K&&primo==false)
primo=true;
else if (P[i]>K&&primo==true)
{
i--;
N--;
P.erase(P.begin()+i);
}
}
int tab[N+1][K+1];
for (int n=0; n<=N; n++)
{
for (int k=0; k<=K; k++)
{
if (n==0||k==0)
tab[n][k]=0;
else if (k==1&&n!=0)
tab[n][k]=P[0];
else if (tab[n][k-1]>=k)
tab[n][k]=tab[n][k-1];
else if (tab[n-1][k]>=k)
tab[n][k]=tab[n-1][k];
else
tab[n][k]=max (P[n-1]+tab[n-1][k-P[n-1]], tab[n-1][k]);
if (P[n-1]>K)
tab[n][k]=min (tab[n][k], P[n-1]);
}
}
return tab[N][K];
}
}
int main ()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
bool uguale=false;
int N, K, x;
cin>>N>>K;
for(int i=0; i<N; i++)
{
cin>>x;
P.push_back(x);
if (K==x)
uguale=true;
}
cout<<mangia (N, K, uguale);
return 0;
}
Ciao, anche se il tuo algoritmo ora fa qualche punto in più la logica di fondo rimane la stessa ed è sempre quella di restituire l’insieme massimo delle portate di peso superiore a K come in questo input:
4 15
20 9 8 16
in cui il tuo programma restituisce 17 invece di 16.
Invece di partire dalla quantità minima = 0 che può mangiare per cercare la quantità massima >= K come il tuo algoritmo in pratica fa, inverti la logica iniziando dalla quantità massima = MAX che può mangiare per arrivare alla quantità minima >= K delle portate da mangiare.
In dettaglio, per le librerie c++ che hai incluso nel programma, non occorre implementare le funzioni min() e max();