#include 
#define MAXN 2000
#define MAXK 1000
using namespace std;
int matrix[MAXN][MAXK + 1];
//int cost[MAXN], profit[MAXN];
int cost[3] = { 8, 6, 4 };
int profit[3] = { 16, 10, 7 };
int knapsack(int n, int k)
{
    int c;

    for(int i = 0; i < n; i++)
        for(int j = 0; j <= k; j++)
            matrix[i][j] = 0;

    for(int i = cost[0]; i <= k; i++)
        matrix[0][i] = profit[0];

    for(int i = 1; i < n; i++)
        for(int j = 0; j <= k; j++) {
            if(j - cost[i] >= 0)
                c = matrix[i - 1][j - cost[i]] + profit[i];
            else
                c = 0;

            if(c < matrix[i - 1][j])
                c = matrix[i - 1][j];

            matrix[i][j] = c;
        }

    return matrix[n - 1][k];
}
int main()
{
    printf("max value = %d\n", knapsack(3, 10));
    return 0;
}