Vorrei imparare il 3D :) (eserc PD) [c++]

[Giova411]

Ecco come contare tutti i modi possibili (non abbiamo limiti dati da alcun k però)
Ossia se R = 5 ed abbiamo v1 = 1 , v2 = 2 , v3 = 5 (quindi 3 monetine diverse)
Il risultato è 4 (ossia tutti i modi possibili senza vincoli su k)
Ecco il codice:

//#include <cstdio>
#include <vector>
//#include<iostream>
#include <fstream>
using namespace std;

int
conta (vector < int >&B, int n, int t)
{
  vector < int >appunti;
  appunti.resize (t + 1, 0);	//inizializziamo tutto a 0
  appunti[0] = 1;		// caso in cui non possiamo dare il resto 
  for (int i = 0; i < n; i++)	//tutti i tagli vengono valutati aggiornando la nostra annotazione
    for (int j = B[i]; j <= t; j++)
      appunti[j] += appunti[j - B[i]];	// risparmiamo lo spazio O(n)
  return appunti[t];
}
int main (void){
  int T, N;
  ifstream in ("in.txt");
  in >> T >> N;
  vector < int >B (N);
  for (int i = 0; i < N; i++) 
     in >> B[i];
  ofstream out ("out.txt"); 
  out << conta (B, B.size (), T) << endl;
  return 0;
}

Quello che rompe ora è k
Sicuro, ed è un metodo che vorrei imparare a fare, si potrebbe gestire il numero fissato k con un vettore a TRE DIMENSIONI:
B [ m, R , k ]

m : contiene i pezzi v1..vn che possiamo utilizzare per il cambio
r : la cifra R da raggiungere
k : è il numero richiesto che fissa il numero di pezzi

[vict85]

Esiste un metodo lineare per determinare il numero minimo di monete utilizzabili. Se questo numero minimo è minore di \(k\) allora la risposta è si, altrimenti è no.

[Giova411]

I tagli vengono tutti dati (tutti diversi tra loro) e possono essere memorizzati in un vettore.
Il problema richiede solo true o false, ma magari si potrebbe dire il numero possibile e, se non si può, dare -1.
Ma il mio scopo è usare un cavolo di array a tre dimensioni con la PD
Da settimane che ci provo (non al problema specifico di questo Topic).
Già lavorare con la PD è cosa ardua... Con un vettore [x,y,x] non ci sono mai riuscito
Tra l'altro non trovo mai esempi degni di nota

[vict85]

Il problema è che sbaglio problemi. Avendo monete infinite ti basta usare una cosa del tipo:

int num_min = 0;
for(int i = N-1; i >= 0; --i)
{
	num_min += resto_rimanente / valore[i];
	resto_rimanente %= valore[i];
}

[Giova411]

Non ho capito se non ho spiegato bene il problema: è una variazione che complica quello classico presente in molti testi. La variazione è che fissa il numero di monete ammesse alla soluzione; non ammette un numero minore o uguale ma esattamente un numero k.
Ora sicuro te hai "approfittato" del tuo sapere matematico per dare una soluzione corretta senza sbattersi con la PD
Riuscendo a lavorare con una tabella a tre dimensioni possiamo usare niente popò di meno che la MemoizationForm!
Una sorta di utopia proiettata in una dimensione spazio-temporale indefinita