Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Find the minimum subset sum difference
//Microsoft (R) Visual C# Compiler version 3.4.0-beta4-19562-05 (ff930dec) //Copyright (C) Microsoft Corporation. All rights reserved. using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace Rextester { public class Program { public static void Main(string[] args) { int[] arr = new int[] {2, 3, 7}; Console.WriteLine("Minimum subset sum difference: " + MinSubsetSumDiff (arr)); } private static int MinSubsetSumDiff (int[] arr) { int maxSum = arr.Sum(); bool[,] t = new bool[arr.Length+1, maxSum+1]; for (int i=0; i < t.GetLength(0); i++) { for (int j=0; j < t.GetLength(1); j++) { if (j == 0) { t[i, j] = true; continue; } if (i == 0) { t[i, j] = false; continue; } if (arr[i-1] <= j) { t[i, j] = t[i-1, j - arr[i-1]] || t[i-1, j]; } else { t[i, j] = t[i-1, j]; } } } int minDiff = Int32.MaxValue; for (int i=maxSum/2; i >=0; i--) { if (t[arr.Length, i] == true) { minDiff = (maxSum - i) - i; break; } } return minDiff; } } }
run
|
edit
|
history
|
help
0
reverse array
Tttt
Enumeration
congtodien
Lazy XML selection
Vajdalinky
lab
sdfgrthyjuytgr
delete_xml_empty_tags
Interface With Ambiguity Problem