plecaki

#include <iostream>
#include<stdio.h>

using namespace std;


int max(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}

int knapSack(int W, int wt[], int val[], int n)
{
   int K[n+1][W+1];

   for (int i = 0; i <= n; i++)
   {
       for (int j = 0; j <= W; j++)
       {
           if (i==0 || j==0)
               K[i][j] = 0;
           else if (wt[i-1] <= j)
                 K[i][j] = max(val[i-1] + K[i-1][j-wt[i-1]],  K[i-1][j]);
           else
                 K[i][j] = K[i-1][j];
       }
   }

   return K[n][W];
}

int main()
{
    int val[] = {30, 500, 400};
    int wt[] = {25, 10, 40};
    int  W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}