ivandrofly

knap sack solution with table

Mar 9th, 2021 (edited)
305
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.45 KB | None | 0 0
  1. namespace KnapSackProblem
  2. {
  3.     using System;
  4.     using System.Collections.Generic;
  5.     using System.Text;
  6.  
  7.     public class KnapSackSolution2
  8.     {
  9.         public static int Test()
  10.         {
  11.             int[,] data = { { 2, 3 }, { 3, 4 }, { 4, 5 }, { 1, 6 } };
  12.             return FindMax(data, 8);
  13.         }
  14.  
  15.         public static int FindMax(int[,] data, int sackWeight)
  16.         {
  17.             int columns = data.GetLength(0) + 1;
  18.             int[,] result = new int[columns, sackWeight + 1];
  19.             int rows = result.GetLength(1);
  20.  
  21.             //for (int i = 0; i < result.GetLength(0); i++)
  22.             //{
  23.             //    result[0, i] = 0;
  24.             //}
  25.  
  26.             for (int i = 1; i < columns; i++)
  27.             {
  28.                 int profit = data[i - 1, 0];
  29.                 int weight = data[i - 1, 1];
  30.                 for (int j = 0; j < rows; j++)
  31.                 {
  32.                     if (weight > j)
  33.                     {
  34.                         result[i, j] = result[i - 1, j];
  35.                     }
  36.                     else
  37.                     {
  38.                         int r = Math.Max(result[i - 1, j], profit + result[i - 1, j - weight]);
  39.                         result[i, j] = r; // find max profix
  40.                     }
  41.                 }
  42.             }
  43.  
  44.             // return the result which will be found in latest row and column
  45.             return result[result.GetLength(0) - 1, sackWeight];
  46.         }
  47.     }
  48. }
  49.  
Add Comment
Please, Sign In to add comment