java - Knapsack algorithm optimized for weight instead of values -

-

is possible modify 1-0 knapsack algorithm optimize final total weight of items in bags first choice (and values second choice), maintaining same algorithmic complexity?

i'm working on this java implementation (in end of article).

more specifically, i'm thinking of changing piece of code 

if (wt[item-1]<=weight){     v[item][weight]=math.max (val[item-1]+v[item-1][weight-wt[item-1]], v[item-1][weight]); }else{     v[item][weight]=v[item-1][weight]; }

with other condition firstly control if weight closer threshold adding item , than, if weight not change, if value better.

have got idea how without change complexity?

thank you

edit with "firstly control if weight closer threshold adding item" mean reaching weight limit of backpack. in other words "maximizing weight can carry in bag" without breaking it

are trying following? choose items weight maximized, while still respecting weight limit. if there multiple optimal solutions each achieve maximum possible weight, choose among them choosing solution has largest total value.

if so, suggest following. (i'm thinking knapsack problem , not java implementation of it.)

let m = maximum value [edited] among items , n = number of items. replace each value (in objective function) weight + value/mn.

then model maximize total weight, while still respecting weight limit. , if there multiple solutions same optimal weight, choose 1 maximum value. dividing mn ensures you'll never choose solution better value @ expense of worse weight.


Comments

Post a Comment

Popular posts from this blog

java - Oracle EBS .ClassNotFoundException: oracle.apps.fnd.formsClient.FormsLauncher.class ERROR -

-
i need in configuring java on machine because, when try loading forms, loader goes in circles , gives error: java.lang.classnotfoundexception: oracle.apps.fnd.formsclient.formslauncher.class @ sun.plugin2.applet.applet2classloader.findclass(unknown source) @ sun.plugin2.applet.plugin2classloader.loadclass0(unknown source) @ sun.plugin2.applet.plugin2classloader.loadclass(unknown source) @ sun.plugin2.applet.plugin2classloader.loadclass(unknown source) @ java.lang.classloader.loadclass(unknown source) @ sun.plugin2.applet.plugin2classloader.loadcode(unknown source) @ sun.plugin2.applet.plugin2manager.createapplet(unknown source) @ sun.plugin2.applet.plugin2manager$appletexecutionrunnable.run (unknown source) @ java.lang.thread.run(unknown source) i have tried re-installing firefox, older versions of java runtime environments, disabling proxy. what missing? application working on other machines. i spent around 100 hours finding s
Read more

c# - how to use buttonedit in devexpress gridcontrol -

-
Image
i trying create gridcontrol buttonedit in 1 of columns. when user clicks button edit, popups form select product. when selection done on popup, returns datarow selection main grid below. but when column loses focus, value wrote column disappear. here code creates gridcontrol's data , buttonedit's click event. private void frmsiparisnew_load(object sender, eventargs e) { dt = new datatable(); dt.columns.add("malzeme_kodu",typeof(string)); dt.columns.add("malzeme_aciklama", typeof(string)); dt.columns.add("adet", typeof(decimal)); dt.columns.add("birim", typeof(string)); dt.columns.add("fiyat", typeof(decimal)); dt.columns.add("kur", typeof(string)); dt.columns.add("tutar", typeof(decimal)); datarow dr = dt.newrow(); dt.rows.add(dr); gc.datasource = dt; } private void repositoryitembuttoneditmal
Read more

nvd3.js - angularjs-nvd3-directives setting color in legend as well as in chart elements -

-
good morning i using angularjs-nvd3-directives, great, having difficulties when setting color of multi bar chart ( http://cmaurer.github.io/angularjs-nvd3-directives/multi.bar.chart.html ). the show legend works well: <div ng-controller="examplectrl"> <nvd3-multi-bar-chart data="exampledata" id="showlegendexample" width="550" height="300" showxaxis="true" showyaxis="true" xaxistickformat="xaxistickformatfunction()" showlegend="true"> <svg></svg> </nvd3-multi-bar-chart> </div> but when add option in conjunction color="colorfunction()" where, var colorarray = ['#ff0000', '#0000ff', '#ffff00', '#00ffff']; $scope.colorfunction = function() { return function(d, i) { return colorarray[i]; }; } the color of cha
Read more