Modulus regning

http://www.google.dk/search?q=greedy+algorithm+coin&btnG=S%C3%B8g&hl=da

der skulle være noget at kigge på.

#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

class RandomClass
{
public:
  RandomClass()
  {
      srand(time(0));
  }

  int operator()(int aRange)
  {
      return int(1.0*aRange*rand()/RAND_MAX);
  }
};


int main()
{
  std::cout << "Indtast beloeb: ";
  int Sum;
  std::cin >> Sum;
  std::vector<int >Pile;
  int i;
  for(i = 0; i < 10; i++)
    Pile.push_back(5);
  for(i = 0; i < 20; i++)
    Pile.push_back(10);
  for(i = 0; i < 5; i++)
    Pile.push_back(2);
  for(i = 0; i < 20; i++)
    Pile.push_back(20);

  RandomClass Random;
  for(int TryCount = 0; TryCount < 10000; TryCount++)
  {
      std::random_shuffle(Pile.begin(), Pile.end(), Random);
      std::vector<int >Temp;
      int CurSum = Sum;
      std::vector<int>::const_iterator it;
      for(it = Pile.begin(); CurSum > 0 && it != Pile.end(); ++it)
      {
        CurSum -= *it;
        Temp.push_back(*it);
      }
      if(CurSum == 0)
      {
        std::cout << "Here we go: ";
        std::copy(Temp.begin(), Temp.end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
        return 0;
      }
  }
  std::cout << "Failed to find a solution :-(" << std::endl;
}

bertelbrander - > Det virker fint tak .. Det ser bare lidt uoverskueligt ud for mig da jeg næsten er nybegynder i C ..

RandomClass er blot en hjælpe class til at generere tilfældige tal i et range.

Pile er stakken med de mønter du har at starte med.
push_back bliver brugt til at tilføje mønter til stakken.

std::random_shuffle blander Pile tilfældigt.

for loopen med (it = Pile.begin(); ...) tager fra starten af Pile indtil den rammer beløbet eller får for meget.

Temp er en liste med de mønter der blev valgt.

if(CurSum == 0) bliver sandt hvis for loopen fra før ramte det rigtige beløb.

std::copy kopierer i dette tilfælde de valgte mønter til std::cout, dvs de bliver udskrevet.

Hejsa!

Har du fået løst problemet?
Hvis ikke, har jeg skrevet en bitte algoritme som løser dit problem, og som modsat bertelbranders forslag altid returnerer det korrekte resultat. Det er nok lidt svært at gennemskue hvad den laver (den benytter en teknik kaldet dynamisk programmering), men du kan bare sige til hvis du vil have en nærmere forklaring.


#include <iostream>
#include <limits.h>

#define N 4 //antal forskellige mønter

int coin_value[N] = {20,10,5,2}; //mønternes værdier
int coin_has[N] = {20,20,10,5}; //disponible mønter af de forskellige slags
int solution[N] = {0,0,0,0}; //løsningen


void invalidate(int coins[]) {
  for (int i=0; i<N; i++) coins[i] = -1;
}

bool isValid(int coins[]) {
  for (int i=0; i<N; i++)   
    if (coins[i] < 0) return false; 
  return true;
}

int numCoins(int coins[]) {
  int res = 0;
  if (!isValid(coins)) return INT_MAX;
  for (int i=0; i<N; i++) res += coins[i]; 
  return res;
}


void calc_coins_needed(int neededSum) {

  int needed_coins[neededSum+1][N];

  for (int j=0; j<N; j++) needed_coins[0][j] = 0;
  for (int i=1; i<=neededSum; i++) invalidate(needed_coins[i]);

  for (int sum = 1; sum<=neededSum; sum++) {

    for (int coin_type = 0; coin_type<N; coin_type++) {

      if ((coin_value[coin_type] <= sum)
          && (numCoins(needed_coins[sum - coin_value[coin_type]]) < numCoins(needed_coins[sum]))
          && (needed_coins[sum - coin_value[coin_type]][coin_type] < coin_has[coin_type])  ) {
        for (int j=0; j<N; j++)
          needed_coins[sum][j] = needed_coins[sum - coin_value[coin_type]][j];
      needed_coins[sum][coin_type]++;
        }
    }
   
  }
   
  for(int j=0; j<N; j++) solution[j] = needed_coins[neededSum][j];
}



int main() {
  int price;
  cout << "Indtast pris: ";
  cin >> price;
  calc_coins_needed(price);
  if (!isValid(solution)) cout << "Kan ikke betale beløbet!" << endl;
  else for (int i=0; i<N; i++) cout << solution[i] << " x " << coin_value[i] << endl;
}

bertelbranders løsning bruger STL? Kan man det i C?

jimbo22s bruger streams?

Det der giver den letteste kode er vel bare at prøve alle muligheder:
Start med en 2 kr. Så er der 48 kr tilbage. Så starter du igen med 2 kr. Så er der 46...
Så tager du en 5 så er der 45 kr tilbage, så tager du en 2 kr ...

Løsninger er selvf dem hvor du ender med 0 til sidst. Ender du med noget negativt er duer sekvensen af mønter ikke.

Man kan ikke bruge stl eller iostreams i C, men der er næsten ikke nogen der programmer i C i vore dage.
Det er ret let at lave eksemplerne om til ren C, hvis det ønskes.

tuxic har ret i at man selvfølgelig kan prøve alle muligheder. Udover at det er en ret ineffektiv måde at løse problemet på, giver det ikke nødvendigvis en optimal løsning i forhold til hvor mange mønter man betaler med. Så ønsker man at betale med så få mønter som muligt er man nødt til bruge dynamisk programmering (eller lignende) for at løse problemet.

jimbo22: det kan vist ikke være rigtigt. Hvis man prøver alle muligheder må man også prøve den optimale.
Man kan overveje om dette er en variant af rygsækproblemet (tror jeg det er) og så fald er der næppe andre muligheder end at prøve alle.

bertelbrander: I know, men efterspurgte needhelpnow ikke løsninger i C?

Jo, men han accepterede en C++ løsning -> mange der spørger her er ikke klar over at der er forskel.

tuxic: jo ok, hvis man prøver alle muligheder og altså fortsætter søgningen selv efter man har fundet en gyldig løsning vil man finde den optimale løsning, problemet er jo bare at metoden har en udførselstid på O(2^n) hvor n er det samlede antal mønter (ikke kun antal mønter af forskellig værdi) hvilket er utilgiveligt langsomt, og her snakker vi ikke kun worst case men også best case. Slutteligt, hvis du sætter dig ned og funderer lidt over problemet vil du se at det faktisk kan løses med dynamic programming (og at min løsning er korrekt).