Variation of knapsack with subexponential growth

Question

So I've come across an interesting problem I'd like to solve. It came across when I was trying to solve a game with nondeterminstic transitions. If you've ever heard of this problem or know if it has a name/papers written about it let me know! Here it is.

Given n boxes and m elements where n1 has i1 elements, n2 has i2 elements, etc (i.e i1 + i2 + ... + in = m). Each element has a weight w and value v. Find a selection of exactly one element from each n boxes (solution size = n) such that the value is maximized and the weight <= k (some input parameter).

The first thing I noticed is there are i1*i2...*in solutions. This is less than m choose n, which is less than 2^m, so does this mean the problem is in P (sorry my math is a little fuzzy)? Does anyone have any idea of an algorithm that does not involve iterating over every solution? Approximations are fine!

Edit: Okay so this problem is actually identical to the knapsack problem, so it's NP-hard. Let the boxes have two elements each, one of zero size and zero value, and one of nonzero size and nonzero value. This is identical to knapsack. Can anyone think of a clever pseudopolynomial time algorithm/conversion to knapsack?

Answer 1

This looks close enough to http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem that almost the same definition of m[i, w] as given there will work - let m[i, w] be the maximum value that can be obtained with weight <= w using items up to i. The only difference is that at each stage instead of considering either taking an item or not, consider which of the possible items at each stage you should take.