Calcolo di tutte le combinazioni possibili!

[Avatar89]

DATI DI INPUT
Il file input.txt contiene nella prima riga un intero positivo N che rappresenta il numero di
monete diverse disponibili. La seconda riga contiene un intero positivo R che rappresenta il
resto da consegnare al cliente. Ciascuna delle successive N righe contiene un intero positivo
che indica il valore di ogni singolo tipo di moneta.

DATI DI OUTPUT
Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il numero
di tutte le possibili combinazioni di monete per la consegna del resto R (notare che possono
essere usate più copie dello stesso tipo di moneta, per esempio 6 monete da cinque
centesimi).

ASSUNZIONI
1 < N <= 100.
1 < K <= 100.

ESEMPIO
File input.txt
8
6
1
2
5
10
20
50
100
200
File output.txt
5


allora,, per adesso ho fatto solo questo, dal momento che non so più andar avanti,, per calcolarne tutte le possibili combinazioni,, ho pensato che prima deve selezionare tutte le sue monete disponibili,, poi dopo fare le combinazioni anche con ripetizione del valore della stessa moneta per trovare il resto,, solo che non so come realizzare questo in codice java,, ho bisogno dei consigli e magari una formula,,,,, grazie,,

import java.util.Scanner;
import java.io.*;

public class Lino {
    public static void main(String args[]) throws Exception {
    Scanner filein=new Scanner (new FileInputStream("input.txt"));

        int N, R, A;

        N=filein.nextInt();
        
        do {
            R=filein.nextInt();
           do {
               while (filein.hasNext()){
               A = filein.nextInt();
               switch (A){
                   
               }
    
               }
           }  while(1<R || R<=100);
        } while(1<N || N<=100);

      } // main
   } // end public class

[Avatar89]

vi, prego,,, che qualcuno mi dia una risposta??,, ho assolutamente bisogno del aiuto,,

[andbin]

Ho letto la tua descrizione del problema ma devo dire che non è chiarissima. Quello che si capisce innanzitutto è che hai a che fare con le "combinazioni con ripetizioni". Fin qui ok.

Nelle "assunzioni" indichi 1 < K <= 100 ma cosa è quel K??? Ti sei sbagliato e volevi mettere R?? Allora forse avrebbe già più senso.

Quindi vediamo se è così: tu vuoi sapere quante sono le combinazioni di monete (anche con ripetizioni di una moneta) tali per cui la somma sia inferiore/uguale a 100???

Ma poi ancora un'altra cosa: in generale le combinazioni e le disposizioni hanno 2 parametri: un valore 'n' che indica il numero di elementi e un valore 'k' che indica la "classe" ovvero il numero di elementi nella combinazione.
Nel tuo caso 'k' quanto vale o da dove è dedotto/imposto???

Prendiamo 4 monete: 1 2 5 10 cioè n=4

Con k=2 si hanno le combinazioni con ripetizioni:
1 1
1 2
1 5
1 10
2 2
2 5
2 10
5 5
5 10
10 10

Con k=3 si hanno le combinazioni con ripetizioni:
1 1 1
1 1 2
1 1 5
1 1 10
1 2 2
1 2 5
1 2 10
1 5 5
1 5 10
1 10 10
2 2 2
2 2 5
2 2 10
ecc...
...

Quindi tu cosa devi fare?? Generare tutte le combinazioni per qualunque valore di k tra 1 e n???

Purtroppo non è chiaro ... almeno a me personalmente non è chiaro. Cerca di chiarire queste questioni e a quel punto si potrà studiare cosa fare.
Non partire in quarta se non sono chiare queste cose.

[Avatar89]

IL PROBLEMA
Il giornalaio Lino è un appassionato di matematica e, prima di consegnare il resto ai propri
clienti, si diverte a calcolare mentalmente quante differenti possibilità esistono per consegnare
tale resto. Ad esempio, considerando l'Euro come valuta, per consegnare 6 centesimi di resto
esistono le seguenti 5 possibilità:
* 6 monete da un centesimo,
* 4 monete da un centesimo e 1 da due centesimi,
* 2 monete da un centesimo e 2 da due centesimi,
* 1 moneta da un centesimo e 1 da cinque centesimi,
* 3 monete da due centesimi.
Lino si sta però accorgendo che a causa della lentezza nella consegna del resto sta perdendo
molti clienti. Pertanto, aiuta Lino a calcolare il numero di possibili combinazioni.

risposte:

si deve calcolare tutte le possibili combinazioni anche con ripetizione per avere il resto, avendo a disposizione certe monete

per K,, hmm,, adesso che c penso mi viene infatti un dubbio,, ehehe,, perchè il problema, me lha dato un mio amico,, potrebbe essere il resto R ma potrebbe essere anche la classe,,

Prendiamo 4 monete: 1 2 5 10 cioè n=4

Con k=2 si hanno le combinazioni con ripetizioni:
1 1
1 2
1 5
1 10
2 2
2 5
2 10
5 5
5 10
10 10

Con k=3 si hanno le combinazioni con ripetizioni:
1 1 1
1 1 2
1 1 5
1 1 10
1 2 2
1 2 5
1 2 10
1 5 5
1 5 10
1 10 10
2 2 2
2 2 5
2 2 10
ecc...
...

la questione è: avendo queste combinazioni,, quante di queste dà il resto che cerchi esempio,,, se cerchi il resto=6,, solo le combinazioni,, 1+5,, 2+2+2,, e quindi l'output sarebbe 2,,,
spero di chiarire alcuni questioni, dandoti questa risposta,,

[Avatar89]

ecco tutto,,,,

IL PROBLEMA
Il giornalaio Lino è un appassionato di matematica e, prima di consegnare il resto ai propri
clienti, si diverte a calcolare mentalmente quante differenti possibilità esistono per consegnare
tale resto. Ad esempio, considerando l'Euro come valuta, per consegnare 6 centesimi di resto
esistono le seguenti 5 possibilità:
* 6 monete da un centesimo,
* 4 monete da un centesimo e 1 da due centesimi,
* 2 monete da un centesimo e 2 da due centesimi,
* 1 moneta da un centesimo e 1 da cinque centesimi,
* 3 monete da due centesimi.
Lino si sta però accorgendo che a causa della lentezza nella consegna del resto sta perdendo
molti clienti. Pertanto, aiuta Lino a calcolare il numero di possibili combinazioni.

DATI DI INPUT
Il file input.txt contiene nella prima riga un intero positivo N che rappresenta il numero di
monete diverse disponibili. La seconda riga contiene un intero positivo R che rappresenta il
resto da consegnare al cliente. Ciascuna delle successive N righe contiene un intero positivo
che indica il valore di ogni singolo tipo di moneta.

DATI DI OUTPUT
Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il numero
di tutte le possibili combinazioni di monete per la consegna del resto R (notare che possono
essere usate più copie dello stesso tipo di moneta, per esempio 6 monete da cinque
centesimi).

ASSUNZIONI
1 < N <= 100.
1 < K <= 100.

ESEMPIO 1
File input.txt
8
6
1
2
5
10
20
50
100
200
File output.txt
5

ESEMPIO 2
File input.txt
6
6
5
10
20
50
100
200
File output.txt
0

[Reiuky]

Scusa, non riesco a capire che significa "il numero di monete diverse disponibili"

Si intende il massimo numero di monete da dare di resto?

[Avatar89]

Scusa, non riesco a capire che significa "il numero di monete diverse disponibili"

Si intende il massimo numero di monete da dare di resto?

per esempio,,,,

nell'esempio 1 le monete che ha a disposizioni sono 1,2,5,10,20,50,100,200
nell'esempio 2 sono 5,10,20,50,100,200

[Reiuky]

Capito... è un'informazione ridondante....

Secondo me una soluzione è:
fare un algoritmo che crei tutte le possibili combinazioni, faccia la somma e controlli se il risultato sia uguale al resto desiderato.

Il modo + semplice è: sapenso che la moneta più piccola DEVE essere 1 (non importa se hai la moneta o meno: dato che il file è di numeri interi il più basso è 1), al max puoi fare combinazioni di 6 monetine.

Quindi con un doppio indice scorri la matrice e fai tutte le combinazioni, sommando i numeri, bloccando ogni volta che trovi un risultato uguale o superiore a 6, e poi aggiungendo 1 all'output se il risultato è 6

(ovviamente prima di tutto ti crei l'array, altrimenti ci mette un secolo il programma a leggere ogni volta il file in in)

[Avatar89]

Quindi con un doppio indice scorri la matrice e fai tutte le combinazioni,

in che senso doppio indice?? ,,,,

[Reiuky]

Niente... scusa... l'ho provata e non viene corretta. Adesso ci penso e vedo se trovo un algoritmo utile.