Hei,
Jeg har et optimeringsfag på universitetet hvor vi har om blant annet Dynamisk Programmering. Slik jeg har forstått det så går det ut på at man løser små delproblemer, lagrer informasjonen og bruker løsningen til å løse et større problem.
Vi har en oppgave som går ut på at man har en lommebok som har plass til 5 mynter og man har 3 forskjellig type mynter: $1, $2 og $5. Hva er den minste verdien man kan kombinere myntene slik at de ikke får plass i lommeboken (som har kun plass til 5 mynter)?
Jeg googlet litt for å få inspirasjon og fant en kode som hevder å løse problemet med dynamisk programmering:
Kode
public class HelloWorld{
public static void main(String []args)
{
int i,j;
int sum=0,count=0,a=0;
int temp=0;
for(i=1;i<=25;i++)
{ count=0;sum=0;j=i;
if(j>=5)
{
temp=j/5;
sum=sum+temp*5;//sum of the coins
count=count+temp;//count the no.of coins
j=j-(temp*5);
}
if( j>=2)
{
temp=j/2;
sum=sum+temp*2;
count=count+temp;
j=j-(temp*2);
}
if(j>=1)
{
temp=j/1;
sum=sum+temp*1;
count=count+temp;
j=j-(temp*1);
}
if(count <=5) //if the count is less than 5 means FIT INTO wallet
{
if(sum==i){ // it is FIT INTO wallet and created
// System.out.println( i+" is created");
}
}
else
{
temp=i/5;
temp=temp+(5-temp);//add 5th coin with $5
sum=temp*5;
count=temp;
if(count <=5)
if(sum !=i)
System.out.println(i+" is the smallest value not created but fit into wallet");
break;
}
}
}
}
Kan noen bekrefte/avkrefte at dette er dynamisk programmering og forklare meg eventuelt hvorfor? For meg virker det som helt vanlig programmering.