I found implementation using 2D array. But how to implement it using 1D array and if it is not possible then why???
Yes 0-1 knapsack can be implemented using 1D array. But by doing so we compensate on the fact that we will not be able to obtain the exact items in the optimal solution which we could when we used 2D array.
The code almost remains the same. Just use two 1-D array instead.
1 Like
But I have seen that using 2D array causes RE for large input.
@beshamberc Of course it would. Let’s understand this by the following means: You have total capacity and elements of the knapsack equal to 10^6. If you take a 2-D array, you need space to store 10^6 * 10^6 elements. Now, since capacity is 10^6, int won’t work to define the datatype so, you choose long. Now, one long type data takes memory of 4B (it may differ according to architecture but let’s have a rough idea) and then for storing 10^6 * 10^6 long ints, you need 10^6 * 10^6 * 4 B of memory, no online judge provides as much memory for your code and hence some elements of array are left out but hey you have already written a loop that should access those left out elements and since they are not found, i.e. you are making a reference to/trying to access an element that does not even exist in the memory and hence, you are awarded with RTE (SIGSEGV) by online judge.
Thus, whenever there are large inputs and you are using DP/ any other algo requiring 2-D array which is going to take lot of space, optimize your algo. Look at the rows and columns which are needed to calculate results, store just those rows/ columns in 1-D arrays and carry on with the algorithm the same way. Voila! You crossed the barrier of memory.
1 Like
Yes, it’s possible.
W : Weight Array
V : Value Array
K : Capacity of knapsack
X[K] : Array of size K to store your result. X[i] corresponds to maximum total value of items you can put in a knapsack of capacity i.
Item i corresponds to weight W[i] and value V[i] for 1<=i<=n
for i from 1 to n
for j from K down to W[i]
X[j] = max(X[j],X[j-W[i]]+V[i])
Your required answer is simply X[K].
2 Likes
@aj95 can you plz explain it more.? i solved 0/1 knapsack problem by using 2 1-D arrays but i can’t understand how to solve it by using 1 1-D array…?
