algorithm - How to assign N numbers into M pack that minimize some target function? -


i have n(for example 30) integer numbers v[i], , m(for example 8) packs, each pack have expected value p[j].

i want assign each integer number 1 pack, following expression calculate difference between sum of v[k] in pack j , expected value of pack j.

diff[j] = abs(p[j] - sum(v[k] in pack j))

the target find best solution minimize sum(diff[j]).

i don't know what's type of kind of problem. can solved linear programming, or np-complete problem?

regardless of whether np-hard or not, may able efficiently solve problem problem instances need using accessible integer programming software. problem, define x_{ij} define if x[i] assigned group j. define variables d_j, diff[j] in formulation. model is:

min_{x, d} \sum_{j=1}^m d_j s.t.       d_j >= p[j] - \sum_{i=1}^n x[i]x_{ij} \forall j            d_j >= \sum_{i=1}^n x[i]x_{ij} - p[j] \forall j            \sum_{j=1}^m x_ij = 1 \forall            x_{ij}\in \{0, 1\}

this mixed integer optimization model, can solved, instance, using lpsolve or lpsolveapi packages in r or intlinprog function in matlab.


Comments

Post a Comment

Popular posts from this blog

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque...
Read more

jsf - How to ajax update an item in the footer of a PrimeFaces dataTable? -

this visual of table have: +---------+------------+-------------------+ | header1 | header2 | header3 | +---------+------------+-------------------+ | row | input | calc'ed output | | row b | input b | calc'ed output b | | etc.. | etc.. | etc.. | +---------+------------+-------------------+ | total: total calc'ed output | +------------------------------------------+ and stripped-down code: <p:datatable id="mytable" value="#{mybean.somelist}" var="currentitem"> <p:column headertext="header1"> <h:outputtext value="#{currentitem.name}" /> </p:column> <p:column headertext="header2"> <pe:inputnumber value="#{currentitem.inputval}"> <p:ajax event="change" listener="#{mybean.changelistener}" update="outputval outputtotal...
Read more

jquery - Keeping Kendo Datepicker in min/max range -

when user types type in date outside of range, we're trying ensure date gets changed closest min/max. text displayed in date picker not change though thought script changing value() @(html.kendo() .datepickerfor(x => x.dob) .max(new datetime(datetime.now.addyears(-18).year, datetime.now.addyears(-18).month, datetime.now.addyears(-18).day)) .min(new datetime(datetime.now.addyears(-70).year, datetime.now.addyears(-70).month, datetime.now.addyears(-70).day)) .events(e=>e.change("ondobchange")) .htmlattributes(new { required = "required", ng_model = "model.dob" })) <p ng-show="validatestate.submitted && frmmain.dob.$invalid" class="help-block">please select</p> <script> function ondobchange(e) { var d...
Read more