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.