#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <limits.h>

/* Renvoie le plus petit nombre de pièces à utiliser parmis a[0], ..., a[n-1]
   pour décomposer M */
int rendu_monnaie_progdyn(int M, int n, int* a){
	assert(n>=0);
	assert(M >= 0);
	for (int i = 0; i < n; ++i){
			assert(a[i] > 0);
	}	
	
	int** T; // tableau des solutions
	// allocation mémoire et valeurs initiales	
	T = malloc((M+1)*sizeof(int*));
	for (int x = 0; x <= M; x++){
		T[x] = malloc((n+1)*sizeof(int));
		T[x][0] = INT_MAX; //2^31 -1, on considère que c'est +infini
	}
	for (int i = 0; i <= n; i++){
		T[0][i] = 0;
	}
	
	// construction du tableau: ligne par ligne
	for (int x = 1; x <= M; x++){
		for (int i = 1; i <= n; i++){
			if (a[i-1]>x || T[x][i-1] < 1 + T[x-a[i-1]][i]){
				T[x][i] = T[x][i-1];
			} else {
				T[x][i] = 1 + T[x-a[i-1]][i];
			}
		}
	}
	
	int res = T[M][n];
	for (int x = 0; x <= M; x++){
		free(T[x]);
	}
	free(T);
	return res;
}



int main(int argc, char const *argv[])
{
	if (argc <= 1){
		printf("Usage: %s M a1 a2 ... ap\nPour décomposer M avec les pièces a1 ... ap\n", argv[0]);
		return 0;
	}
	int n = argc - 2; // nombres de pièces distinctes
	int M = atoi(argv[1]);
	int* a = malloc(n*sizeof(int));
	for (int i = 0; i < n; ++i){
	 	a[i] = atoi(argv[i+2]);
	} 

	int opt = rendu_monnaie_progdyn(M, n, a);
	printf("Solution trouvée en utilisant %d pièces\n", opt);
	free(a);
	return 0;
}