Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- namespace KnapSackProblem
- {
- using System;
- using System.Collections.Generic;
- using System.Text;
- public class KnapSackSolution2
- {
- public static int Test()
- {
- int[,] data = { { 2, 3 }, { 3, 4 }, { 4, 5 }, { 1, 6 } };
- return FindMax(data, 8);
- }
- public static int FindMax(int[,] data, int sackWeight)
- {
- int columns = data.GetLength(0) + 1;
- int[,] result = new int[columns, sackWeight + 1];
- int rows = result.GetLength(1);
- //for (int i = 0; i < result.GetLength(0); i++)
- //{
- // result[0, i] = 0;
- //}
- for (int i = 1; i < columns; i++)
- {
- int profit = data[i - 1, 0];
- int weight = data[i - 1, 1];
- for (int j = 0; j < rows; j++)
- {
- if (weight > j)
- {
- result[i, j] = result[i - 1, j];
- }
- else
- {
- int r = Math.Max(result[i - 1, j], profit + result[i - 1, j - weight]);
- result[i, j] = r; // find max profix
- }
- }
- }
- // return the result which will be found in latest row and column
- return result[result.GetLength(0) - 1, sackWeight];
- }
- }
- }
Add Comment
Please, Sign In to add comment