Ok, my solution would be: Look at each cnt_i's binary representation and split it into O(logcnt_i) items accordingly. For example, if cnt_i = 259, we split it into 3 items: one with cost c_i * 256 and value v_i * 256, one with cost c_i * 2 and value v_i * 2 and one with cost c_i and value v_i. Though note that this doesn't, for example, account for buying 128 of that item. So we go from the highest bit to the lowest, and if we have at least 1 item that represents the current bit and 0 items that represent the bit that is 2 times less significant, we split one of the items representing that bit into 2 items with 2 times smaller value and cost. Now each of the O(n * log(cnt)) new elements can be chosen 0 or 1 times, which can obviously be solved by knapsack in O(n * C * log(n)).