algorithm - Partition of a set into K disjoint subsets with equal sum -

-

given n ( n <= 20) non-negative numbers. there / can there algorithm acceptable time complexity determines whether n numbers can divided k ( k <= 10) disjoint subsets, such each subset has equal sum?

one way improve on brute force method:

s = sum of numbers = 2 10   k = s /    if k integer     partitions of input array minimum subset size of 2 elements , maximum of n-1 elements.     check each partition it's generated see if subsets have same sum.     end if    next

the hard (and slow) part generating partitions. can recursive function. shouldn't unreasonably slow partitioning 20 numbers. can optimize partition generation throwing out partitions unequal subset sums early.


Comments

Post a Comment

Popular posts from this blog

javascript - How to synchronize the Three.js and HTML/SVG coordinate systems (especially w.r.t. the y-axis)? -

-
i'm combining 3d content three.js html , svg content. three.js cssloader pretty job synchronizing placement of html , svg content in 3d world. but svg/html coordinate systems 'left-handed', whereas three.js coordinate system 'right-handed'. means y-axes reversed. in svg/html, y / top goes go down screen, , three.js uses more standard mathematical convention of y going down go down screen. i have continually convert 1 other, pretty error prone. know not first run (for example, look here ). has come general solution? here's tried: do in object3d .scale.y = -1 . may suspect, turns out disaster. turns inside-out, , don't try put camera in there. do in object3d .rotate.x = math.pi . more promising, z axis no longer consistent html concept of z-index. still, i'm using now. in html, don't use top , use bottom . in svg , inside <g transform="scale(1, -1)"> inside <g transform="translate(0, imageheight)"> . h...
Read more

javascript - How do I find how many occurences are there of a highlighted string, and which occurence is it? -

-
as title says, have website text inside div, there way highlight part of , know occurence is? if text has 4 occurences of word "something", , highlight 3rd, how information using javascript/jquery? http://jsfiddle.net/g09g35xa/6/ here's method seems work. highlight string want , when click button alert index of highlighted word in div. markup: <div id="thediv"> <p>the quick brown quick fox jumps on lazy dog</p> </div> <br /> <input id="findindex" type="button" value="find index of highlighted string" /> and js: function getselectedhtml() { try { if (window.activexobject) { var c = document.selection.createrange(); return c.htmltext; } return getselection().getrangeat(0).tostring(); } catch (e) { if (window.activexobject) { return document.selection.createrange(); } else { return ...
Read more

java - Reading data from multiple zip files and combining them to one -

-
i want read data lets 4 zip files called zip1, zip2, zip3, zip4. of these zip files split 1 big zip file called "bigzip". want combine zip files 1 , compare bytes if 1 bigzip file matches size of bytes combined zip file of (zip1+zip2+zip3+zip4). getting small file size when combine size of 4 zip files. doing wrong? here code same: targetfilepath1, targetfilepath2, targetfilepath3, targetfilepath4 belongs path of 4 zip files. sourcefilepath path bigzip file class test { public static void main(string args[]) { zipoutputstream outstream = new zipoutputstream(new fileoutputstream(sourcebigzip)); readzip(sourcefilepath, targetfilepath1); readzip(sourcefilepath, targetfilepath2); readzip(sourcefilepath, targetfilepath3); readzip(sourcefilepath, targetfilepath4); outstream.close(); } static void readzip(string sourcebigzip, string targetfile) throws exception { zipinputstream instream = new zipinputstream(new file...
Read more