Game Maker Games, Articles, Tutorials & More

Print

ds_list_subset_can_sum

By Daniel · January 4, 2009

Tests whether some subset of the given list has a given sum. The algorithm is fast with small (target) sums, but slow with larger ones.

// ds_list_subset_can_sum(id, sum)
// Tests whether some subset of the list has a given sum
// The algorithm is fast with small target sums, slow with large ones

var L, size, targetSum, canForm, i, E, sum;

// Make a sorted copy of the list so that the sort doesn't affect the original
L = ds_list_create();
ds_list_copy(L, argument0);
ds_list_sort(L, true);
size = ds_list_size(L);

targetSum = argument1;

// 0 can be formed from the summation of the empty set
canForm[0] = true;

// Declare that no other sums can be formed by default
for (i = 1; i <= targetSum; i += 1)
  canForm[i] = false;

// Main loop
for (i = 0; i < size; i += 1) {
  E = ds_list_find_value(L, i);
  // Backward loop avoids the need for two-dimensional storage
  for (sum = targetSum; sum >= E; sum -= 1)
    if (canForm[sum - E])
      canForm[sum] = true;
}

return canForm[targetSum];

Categories: Data processing, Mathematics

Comments

There are no comments to display.

Post a Comment

You must be signed in to post comments.

Advertisement