Pranzo dalla nonna (10/100)

Aiuto
1

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;
}
2

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.

3

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;
}
1 Mi Piace
4

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();

5

Grazie mille, non sono sicura di come dovrebbe venire la matrice ma ci provo