Du må være registrert og logget inn for å kunne legge ut innlegg på freak.no
X
LOGG INN
... eller du kan registrere deg nå
Dette nettstedet er avhengig av annonseinntekter for å holde driften og videre utvikling igang. Vi liker ikke reklame heller, men alternativene er ikke mange. Vær snill å vurder å slå av annonseblokkering, eller å abonnere på en reklamefri utgave av nettstedet.
  7 1778
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.
Sitat av salolina Vis innlegg
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)?
Vis hele sitatet...
Huh? Den minste verdien man kan kombinere myntene slik at de ikke får plass i lommeboken? Du mener... seks enere vil jo være den minste verdien som ikke får plass i lommeboken. Men det var vel ikke helt slik oppgaven var? Har du link til oppgaven, eller kan du sitere den ordrett?

Med forbehold om at jeg ikke forstår et metrisk kvekk av oppgaven din, så kan dette minne litt om en versjon av ryggsekkproblemet (Knapsack problem). Det kan du lese mer om -- og se løsninger med dynamisk programmering -- her:
https://en.wikipedia.org/wiki/Knapsack_problem

Har du forresten testet at den koden du viser til i det hele tatt virker? Uten at jeg kan påberope meg å være noen som helst Javaekspert, så ser det ved første øyekast ut som søplekode.

Kode

temp=j/5;
sum=sum+temp*5;
????
Hvorfor ikke bare skrive sum+=j da?
Intetsigende variabelnavn og meget mangelfull kommentering.

Jeg orker ikke sette meg inn i den koden og hva den gjør, men det ser ut som den i alle fall teller opp fra 1, til den har dekket tilstrekkelig mange alternativer, og dermed muligens produserer en eller annen løsning på veien. Den lagrer det så vidt jeg ser ikke i en tabell eller noe slikt underveis, men hvis den "bruteforcer" seg oppover og hele tiden sjekker mot beste løsning "hittil", så kan det vel muligens funke, I guess. Men å kalle det dynamisk programmering er nok en stretch.

Min soleklare anbefaling er å ta en titt på andre kilder og prøve å skrive en bedre kode selv!


Disclaimer:
Øynene mine holdt ikke ut den koden der i mer enn ca fire og et halvt sekund, så mulig beskrivelsen min av koden er helt på jordet.

Edit:
Denne linjen i koden gjør forresten at jeg skjønner enda mindre av oppgavebeskrivelsen din. Er du sikker på at koden i det hele tatt prøver å løse det problemet du har fått?

Kode

System.out.println(i+" is the smallest value not created but fit into wallet");
Ut fra denne setningen så virker det jo som om koden prøver å finne den minste verdien som får plass i lommeboken men som ikke blir produsert av algoritmen?
...?
Sist endret av Realist1; 30. november 2017 kl. 08:04.
Trådstarter
4 1
Sorry for dårlig forklaring. Her er oppgaven:

Assume you have three type of coins, $1, $2, and $5, and a wallet that fits up to 5 coins. Use
Dynamic Programming to find the smallest value (in whole dollars) that cannot be created and fit
into the wallet. Here are a few examples how values can be created:
• you can create $7 by putting in 1 coin of $5, and 1 coin of $2.
• you can create $18 by putting in 3 coins of $5, 1 coin of $2, and 1 coin of $1.

6 kunne blitt laget med en 5-er og en 1-er, så det er mulig å lage 6 og få plass i lommeboken.

Jeg har testet koden og den ser ut til å fungere. Har prøvd å skrive egen kode selv, men fikk det aldri helt til dessverre

Ok, slik jeg forstår det er koden ubrukelig. Den returnerer riktig svar, men det er ikke dynamisk programmering, selv om den hevder å være det? Takk for tipset med Knapsack. Har lest litt om det, og kanskje det er mulig å gjøre oppgaven til en Knapsack oppgave ved å si at vi ønsker den minste verdien slik at V >= W, hvor V er verdi og W er kapasitet (tilsvarende Knapsack) og istedenfor å maksimere vil vi minimere V. Jeg har prøvd å ta utgangspunkt i Knapsack, men får det ikke til å fungere. Tips tas i mot med stor takknemlighet!
Sist endret av salolina; 30. november 2017 kl. 16:12. Grunn: Automatisk sammenslåing med etterfølgende innlegg.
Trådstarter
4 1
Ok, den løser vel et annet problem strengt tatt. Mulig det er likheter i oppgavene som man kan utnytte. I min oppgave handler det ikke om å veksle penger
nso
popålol
nso's Avatar
Administrator
Nei, det er nøyaktig samme problemstilling og løsningen er forklart veldig enkelt. Det er visst et helt vanlig og basic øvelsesproblem for dynamic programming.
Sist endret av nso; 30. november 2017 kl. 17:06.
For meg ser det ut som vanlig rekursiv programmering. Er dynamisk et nytt navn for det?
Trådstarter
4 1
Nei, dynamisk programmering går ut på at man lagrer verdier underveis når man løser delproblemer som man så bruker på større problemer, slik at man ikke gjør de samme utregningene gjentatte ganger. Så all rekursiv programmering er ikke dynamisk nødvendigvis