algorithm - Solving unbounded knapsack with A* -

-

i'm trying reconcile 2 seemingly contradictory ideas:

  1. the unbounded knapsack optimization problem known np-hard
  2. my colleague , think can solve minor variation on in polynomial time using a*

sounds crazy, right? that's think!

the variation of problem described in terms of cargo plane must unload of goods in order reduce payload plane's capacity. there's set of items each weight , value, , target weight must unloaded -- optimize goods unload have @ least w weight removed, , minimize total value of goods. consider unbounded problem there arbitrarily many items available each of n different types.

the proposed solution uses graph starts @ node (vertex) representing nothing unloaded. each unload operation represents edge, graph grows exponentially out starting point every possible combination of goods unloaded. destination node virtual aggregate in combinations total weight >= target considered target node. total weight unloaded far gets stored in each node , used determine whether target has been reached or not. cost of each edge value of item being unloaded. shortest-path algorithm such dijkstra or a* find optimum set of goods.

dijkstra takes exponential time since exploring possible combinations. admissible heuristic, think a* should run in polynomial time. , think following heuristic should work. every good, calculate "specific value" ratio of value weight. pick highest specific value. heuristic given node, calculate weight still needed unloaded times maximum specific value. provides estimate either correct in case target weight can achieved integer number of optimal goods, or in other cases underestimates distance (weight) remaining because actual number of goods need rounded up. heuristic admissible.

i haven't proven runtime complexity in rigorous way. way a* works, greedily add items towards goal, exploring best options quickly, intuitively feels should run in polynomial time n. , admissible heuristic solution guaranteed optimal.

so what's wrong solution? absolutely not believe have found novel solution well-studied problem applying well-known algorithm. seems should work.

this sounds standard branch , bound method knapsack. it's when there's variety in ratios devolves exponential-time brute force when ratios same.


Comments

Post a Comment

Popular posts from this blog

html5 - What is breaking my page when printing? -

-
Image
i have questioner , don't know why when printing it's creating break before first question. live demo (link) i able resolve issue removing fieldset container had wrapped in.. having fieldset element causing of fields grouped together, , since not fit on first page, being pushed second page. removing fieldset element, able firefox print first 2 questions on page 1 identically chrome. it seems not new problem firefox , fieldset not playing nice found old bugzilla ticket 2008 has persisted , still being commented on in 2014 (link) if retaining fieldset important, found solution else came here (link) <script type='text/javascript'> $(window).bind('beforeprint', function(){ $('fieldset').each( function(item) { $(this).replacewith($('<div class="fieldset">' + this.innerhtml + '</div>')); } ) }); $(window).bind(
Read more

c# - must be a non-abstract type with a public parameterless constructor in redis -

-
when save object, got below error must non-abstract type public parameterless constructor in order use parameter 't' in generic type or method 'servicestack.redis.redisclient.store<t>(t) redisclass.getinstnace().store(msg); // error here redisclass.getinstnace().save(); as third party's class, can not edit how save object? could create wrapper around third party object call constructor, store wrapper? e.g. public class mywrapper { public thirdpartyobject thirdpartyinstance { get; set; } public mywrapper() { thirdpartyinstance = new thirdpartyobject("constructors"); } }
Read more

ajax - PHP/JSON Login script (Twitter style) not setting sessions -

-
i'm having trouble getting twitter style login work properly, reason gets stuck at session_register("useremail"); session_register("userpass"); and doesn't redirect after it. if enter wrong account data, works , appropriate error message pops up. this full code: <?php if(empty($_post['email']) || empty($_post['password'])) { die(msg(0,"all fields required")); } if(!(preg_match("/^[\.a-z0-9_\-\+]+[@][a-z0-9_\-]+([.][a-z0-9_\-]+)+[a-z]{1,4}$/", $_post['email']))) die(msg(0,"you haven't provided valid e-mail")); $host="localhost"; $username="root"; $password="x"; $db_name="x"; $tbl_name="x"; mysql_connect("$host", "$username", "$password")or die("cannot connect"); mysql_select_db("$db_name")or die("cannot select db"); $useremail=$_post['email']; $userpass=
Read more