Skip to content

Instantly share code, notes, and snippets.

@dachev
Created June 8, 2011 04:47
Show Gist options
  • Save dachev/1013791 to your computer and use it in GitHub Desktop.
Save dachev/1013791 to your computer and use it in GitHub Desktop.
Is Measurable
// Actually, this is not going to work. Please ignore it.
function isMeasurable(target, array) {
if (array.length < 1) { return false; }
if (array.indexOf(target) >= 0) { return true; }
var weights = array.concat(target);
var length = 1 << weights.length;
for (var i = 0; i < length; i++) {
var position = weights.length - 1;
var bitmask = i;
var subset = [];
while(bitmask > 0) {
if((bitmask & 1) == 1) { subset.push(weights[position]); }
position--;
bitmask >>= 1;
}
if (subset.length < 2) { continue; }
if (subset.indexOf(target) < 0) { continue; }
var total = sum(subset);
if (total % 2 == 0 && total/2 >= target) { return true; }
}
return false;
}
function sum(subset) {
var sum = 0;
for (var i = 0; i < subset.length; i++) { sum += subset[i]; }
return sum;
}
@dachev
Copy link
Author

dachev commented Jun 12, 2011

Sort of. To be precise:
isMeasurable(8, [5, 6, 9]) => true
isMeasurable(13, [5, 6, 9]) => false

@md2perpe
Copy link

@dachev
Copy link
Author

dachev commented Jun 12, 2011

Cool, this works :-)

@dachev
Copy link
Author

dachev commented Jun 12, 2011

Can you come up with a recursive version?

@md2perpe
Copy link

It worked directly? There wasn't even a typo? Wow...
I'll think about a recursive version.

@md2perpe
Copy link

I've updated my gist with a recursive version (untested).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment