fork(2) download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Test
  6. {
  7. 	public static void Main()
  8. 	{
  9. 		var packSizes = new int[] { 5, 8, 10, 25, 50 };
  10. 		var totalNeeded = 176;
  11.  
  12. 		var result = GeneratePackings(packSizes, totalNeeded);
  13. 		Console.WriteLine(result.Count());
  14. 		var maximal = result.Where (r => r.Zip(packSizes, (a, b) => a * b).Sum() == totalNeeded).ToList();
  15. 		var min = maximal.Min(m => m.Sum());
  16. 		var minPacks = maximal.Where (m => m.Sum() == min).ToList();
  17.  
  18. 		foreach (var m in minPacks) {
  19. 			Console.WriteLine("{ " + string.Join(", ", m) + " }");
  20. 		}
  21. 	}
  22.  
  23. 	// Define other methods and classes here
  24. 	public static List<int[]> GeneratePackings(int[] packSizes, int totalNeeded)
  25. 	{
  26. 		var packings = GeneratePackingsInternal(packSizes, 0, new int[packSizes.Length], totalNeeded);
  27. 		return packings;
  28. 	}
  29.  
  30. 	private static List<int[]> GeneratePackingsInternal(int[] packSizes, int packSizeIndex, int[] packCounts, int totalNeeded)
  31. 	{
  32. 		if (packSizeIndex >= packSizes.Length) return new List<int[]>();
  33.  
  34. 		var currentPackSize = packSizes[packSizeIndex];
  35. 		var currentPacks = new List<int[]>();
  36.  
  37. 		if (packSizeIndex + 1 == packSizes.Length) {
  38. 			var lastOptimal = totalNeeded / currentPackSize;
  39. 			packCounts[packSizeIndex] = lastOptimal;
  40. 			return new List<int[]> { packCounts };
  41. 		}
  42.  
  43. 		for (var i = 0; i * currentPackSize <= totalNeeded; i++) {
  44. 			packCounts[packSizeIndex] = i;
  45. 			currentPacks.AddRange(GeneratePackingsInternal(packSizes, packSizeIndex + 1, (int[])packCounts.Clone(), totalNeeded - i * currentPackSize));
  46. 		}
  47.  
  48. 		return currentPacks;
  49. 	}
  50.  
  51. }
Success #stdin #stdout 0.06s 24360KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
6681
{ 0, 2, 1, 0, 3 }
https://ideone.com/zkCUYZ
language:
C# (gmcs 5.20.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!