DSA interview question

Unbounded Knapsack

Hard · Algorithms · Topics: dynamic programming, unbounded knapsack

The problem

You're building the resource-allocation engine for a cloud infrastructure procurement tool. The company can buy server "packages" — each package has a fixed cost (weight, in terms of budget) and delivers a certain compute value. Unlike a one-time purchase decision, any package type can be bought as many times as you want (there's no limit on how many identical servers you can order). Given a total budget W (knapsack capacity), and arrays of weight[] and value[] for each item type, find the maximum total value achievable without exceeding the budget.

Function signature

int unboundedKnapsack(vector<int>& weight, vector<int>& value, int W);

Test cases

`weight`	`value`	`W`	Output	Explanation
`[1,3,4,5]`	`[10,40,50,70]`	8	110	two items of weight 4 (value 50 each) → 100... verify: actually 3+5=8 → 40+70=110
`[5,10,15]`	`[10,30,20]`	100	300	ten items of weight 10 (value 30 each) → 300
`[1]`	`[10]`	5	50	five items of weight 1 → 50
`[3]`	`[10]`	4	10	can only fit one item of weight 3 (leaves 1 wasted capacity)
`[]`	`[]`	10	0	no items available
`[5]`	`[10]`	3	0	item doesn't fit at all within capacity
`[2,4,6]`	`[3,7,10]`	8	12	two items of weight 4 → 14... verify via code, or 4+4=8→14 or other combos

(Always verify tricky test cases with actual code execution before quoting — unbounded knapsack combinatorics can be non-obvious by hand.)

How interviewers phrase it

"Given item weights and values, and unlimited copies of each item, maximize value within a weight capacity W."
"You can buy the same item multiple times — how much value can you pack into a budget of W?"
Often introduced as a direct contrast right after 0/1 Knapsack: "Now what if you could pick the same item more than once?"

Clarifying questions to ask

Can each item type be used an unlimited number of times, or is there some cap? (Core distinguishing question from 0/1 knapsack — confirm explicitly.)
Are weights and values guaranteed positive? (Zero or negative weight items would allow infinite value — worth flagging as a degenerate case.)
Is W guaranteed non-negative? Are weight/value arrays guaranteed same length?
Do I need just the max value, or also which items (and how many of each) were chosen?
What's the expected range of W and number of item types? (Signals whether O(n·W) DP is acceptable.)

Follow-ups to expect

"How is this different from 0/1 Knapsack?"
"Can you reconstruct which items (and how many of each) were chosen?"
"How does Rod Cutting relate to this?"
"Can you optimize space?"
"What if there's a limited count per item (bounded knapsack, not unbounded)?"
"What if items have a value and cost, and you want minimum cost for a target value (inverse framing)?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview