Problem:

Given $N (1 \le N \le 1000)$ items of value $v_i (1 \le v_i \le 1000)$ and some goal capacity $C (1 \le C \le 10000)$, find the minimum number of items needed to obtain a total value of $C$.

Input (file.in):

Line $1$: Two integers, $C$ and $N$.
Lines $2 \ldots N+1$: One integer, $v_i$.

Output (file.out):

Line $1$: The minimum number of items needed to obtain a total value of $C$.

Solution:

/*
* Example Dynamic Programming Code
* Albert Gural
*/

#include <fstream>

using namespace std;
FILE *fin  = fopen("file.in",  "r");
FILE *fout = fopen("file.out", "w");
int C, N; 	   // C = capacity, N = number of items
int dp[10005]; // dp[i] is min # of items for capacity i
int val[1005]; // val[i] is value of ith item

int main () {
	fscanf(fin, "%d %d", &C, &N);

	// Initialize val array from input
	for(int i = 0; i < N; i++)
		fscanf(fin, "%d", &val[i]);

	// Initialize dp array.  (-1 is infinity)
	dp[0] = 0;
	for(int i = 1; i <= C; i++) dp[i] = -1;

	// Dynamic Programming bottom-up approach
	// For each capacity 1...C, for each item 1...N,
	// dp[i] is given by minimum of
	// including and not including item j.
	for(int i = 1; i <= C; i++) {
		for(int j = 0; j < N; j++) {
			if(val[j] <= i && dp[i - val[j]] != -1) {
				dp[i] = (dp[i] == -1)?
						(dp[i - val[j]] + 1) :
						(min(dp[i], dp[i - val[j]] + 1));
			}
		}
	}

	// We want minimum # items for capacity C.
	fprintf(fout, "%d\n", dp[C]);
	return 0;
}