מריה בוטוסוב

נתונה קבוצת עצמים שלכל אחד מהם משקל ומחיר ותיק מוגבל במשקל, שאפשר להכניס לתוכו. המטרה היא להכניס לתיק מהעצמים הנתונים שסכום משקליהם אינו עולה על החסם הנתון, ומחירו מרבי. כל חפץ אפשר להשתמש רק פעם אחד.

// Data:
 1 // Values (Price) of items (array v)
 2 // Weights of items (array w)
 3 // Number of items (n)
 4 // Knapsack capacity (W)
 
 public static int knapSack(int W, int[] w, int [] v, int n) {
     int [,] K = new int[n + 1, W + 1];
     //Run over all items
     for(int i = 0;i <= n; ++i) {
         //And run over all capacity
         for(int weight = 0; weight <= W; ++weight) {
            //if current item or current weight of this item 0 - set zero to array
            if(i == 0||weight == 0)
                K[i,weight] = 0;
                
            //if current "weight to fill" more or equal to current item weight
            else if(w[i-1] <= weight)
            {
                //choose max between 
                // new addition of value and weight
                // previous stored value and weight
                K[i,weight] = Math.Max(
                    v[i-1] + K[i-1,weight-w[i-1]],
                    K[i-1],weight]
                );
            }
            else
                //set as previous
                K[i,weight] = K[i-1,weight];
         }
     }
     return K[n, W]; //return current value of knapSack
 }