# Dynamic Programming

## 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;
}