Not Yet Answered # wired knapsack...

Ancient Dragon 5,243 Discussion Starter gregorynoob 2 VernonDozier 2,218 Discussion Starter gregorynoob 2 vijayan121 1,152 VernonDozier 2,218 Need some help with this Array. I am trying to get the sum of the even numbers and the sum of the odd numbers using a for each loop. I know the answers to what I am trying to achive are sum of even = 84 and the sum of ...

0

why use recursion when a simple loop will do. Loops are always faster than recursion (and less memory/stack intensive too).

0

a simple loop? could you please tell me what algorithm would that be? cause recursion would go O(n!), would have to check all the combinations, also i didn't say, there are no unlimited supplies of items like in usual knapsack.

0

O (n!) when using recursion? I either don't understand the problem correctly or I think you are doing an extremely inefficent recursion. Post your recursion code. As for the simple loop, if I'm understanding correctly, you would just do something like this?

```
int items[200];
int x; // number of items to add.
// code to fill in above variables
int sum = 0;
for (int i = 0; i < x; i++)
sum += items[i];
```

I have no idea if this is all you are looking for. This comment:

would have to check all the combinations, also i didn't say, there are no unlimited supplies of items like in usual knapsack.

suggests there is more to the problem, but I don't know what you mean. Can you elaborate on the assignment?

0

well i guess it can really be done without DP, as it is not really limited and can be done by going through the sorted array of items from the end to the start, if an item is larger than limit, limit is set to zero and i break the loop, otherwise i subtract the item value from the limit and keep on going. i guess that was what Dragon meant.

0

the general knapsack problem and the subset sum problem are NP-hard, but not NP-incomplete. so there are no polynomial-time algorithms. but it is one of the easy NP-complete problems to solve.

it can be solved (in pseudo-polynomial time) using dynamic programming.

AFAIK, using a Branch and bound algorithm http://en.wikipedia.org/wiki/Branch_and_bound should yield a faster solution. perhaps, you should use a recursive (rather than iterative) Branch and bound. iteration won't give you any significant improvement in performance here.

knuth volume 4 http://www.amazon.com/Art-Computer-Programming-Fascicle-Combinatorial/dp/0321534964 would be the definitive reference.

0

the general knapsack problem and the subset sum problem are NP-hard, but not NP-incomplete. so there are no polynomial-time algorithms. but it is one of the easy NP-complete problems to solve.

it can be solved (in pseudo-polynomial time) using dynamic programming.

AFAIK, using a Branch and bound algorithm http://en.wikipedia.org/wiki/Branch_and_bound should yield a faster solution. perhaps, you should use a recursive (rather than iterative) Branch and bound. iteration won't give you any significant improvement in performance here.

knuth volume 4 http://www.amazon.com/Art-Computer-Programming-Fascicle-Combinatorial/dp/0321534964 would be the definitive reference.

Oh, this is a well known problem? I had never heard of it before and was just going from the description in the first post so I was a little puzzled. I just looked it up on wikipedia and it makes more sense now.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

When I execute this progammatically, I get a table with row heights much larger than when I do this manually.

Note : Sel is the Word.Selection object and the Clipboard contains an Excel Table.

```
public void AddClipboard()
{
Sel.PasteExcelTable(false,false, false);
var t = Sel.Tables[Sel.Tables.Count];
t.AutoFitBehavior(Word.WdAutoFitBehavior.wdAutoFitContent);
}
```

the function that I created to find the ...