# KNPSK - Editorial

Hi Everyone.
I have used different approach but it runs slow.

Sort values and increase value at each iteration uptill capacity is M as per

• current max value of wt 1 or
• current max value of wt 2 - min value of wt 1 which are added added
or
• none and we shall add wt 2 at next one or
• current max value of wt 2 if prev executed

Time complexity is only O(NlogN).
I have got correct answer but it runs very slow :(. It runs in 0.56 seconds. :(.

This problem was easy so upper time bound was not quite tight but I am planning to tackle harder than these. Many of you are already masters in those and thus I am confident that you can help me.

It would be immensely kind of you folks if you could give a little of our valuable time to tell me how to optimize it.
Please, any help is greatly appreciated.
Thanks for sparing some time and reading this.

https://www.codechef.com/viewsolution/14312394

Can anyone tell me whats wrong with my solution https://www.codechef.com/viewsolution/18995198

I went with a priority queue approach with two max heaps one for items having 1 unit weight and other for items having 2 units weight. Pick the bigger of the two by comparing the top of both heaps and check for weights. Pop the items as suitable and compute the next profit.

``````long long int knapsack_01(long long int max_capacity, const std::vector<std::pair<long long int, long long int> > &profit_ratios) {
std::priority_queue<long long int> max_heap_twos, max_heap_ones;
/* Maintain two heaps of items which weight 1 or 2 units into two max heaps and choose whichever one gives higher cost profit. */
for (const auto& items : profit_ratios) {
if (items.first == 1) {
max_heap_ones.push(items.second); // cost.
}
if (items.first == 2) {
max_heap_twos.push(items.second); // cost.
}
}
long long int knapsack_capacity = 0, cost = 0, weight = 0;
while (weight < max_capacity) {
/* Break if all items have been put into the knapsack. */
if (max_heap_ones.empty() && max_heap_twos.empty()) break;
auto two = ((max_heap_twos.empty()) ? 0 : max_heap_twos.top());
auto one = ((max_heap_ones.empty()) ? 0 : max_heap_ones.top());
/* Capacity of a 1 weight item left. */
if ((max_capacity - weight) == 1) {
weight += 1;
cost += one;
/* Item put into knapsack, so pop. */
if (!(max_heap_ones.empty())) max_heap_ones.pop();
break;
}
/* Capacity of a 2 weight item left. */
else if ((max_capacity - weight) == 2) {
weight += 2;
cost += two;
/* Item put into knapsack, so pop. */
if (!(max_heap_twos.empty())) max_heap_twos.pop();
break;
}
/* Capacity left is more.*/
else {
if (one >= two) {
weight += 1;
cost += one;
if (!(max_heap_ones.empty())) max_heap_ones.pop();
}
else {
weight += 2;
cost += two;
if (!(max_heap_twos.empty())) max_heap_twos.pop();
}
}
/* max_capacity is reached why loop further. */
if (weight == max_capacity) break;
}
/* Return the cost. */
return cost;
}
``````

I want to know why this greedy works ? There must be some proof .Can you give me a proof by contradiction ?

proof is almost immediate, think over it and you will find

code is too complex for me to understand, if you want testcase on which it failed, I can give that.

why greedy solution is working ??

proof is simply from the style of construction. Think over it and you can convince yourself.

thanks but donāt need the test casesā¦i have solved both odd and even cases in one go with a couple of if else conditionsā¦if anyone can correct my logic will be highly appreciated.

Thanks for the editorial! Could I know for which test case my code is failing: http://www.codechef.com/viewsolution/4132731
Would it be possible to get the test case inputs and output altogether?

1 Like

Your program fails on this case:

2

1 12

2 1

The correct answer should be 12, 12, 13, but you print out 12, 1, 13. Remember, you donāt necessarily have to fill up the knapsack to its maximum capacity. I made this mistake as well ^.^

10 Likes

@tonynater: Thank you!

You are trying to allocate n*t memory for **dp, as n*t can be as huge as 10^14,you can not allocate this huge amount of memory.So thatās why SIGSEGV. I think maximum memory that you can store in a local array is about 10^6.Where as for global array it can be upto 10^9.

got my code running. If anyone wants to see you can have a look here.
http://www.codechef.com/viewsolution/4134269

This method is a little diffrent than the one in the editorial.

Your code fails on this test case. 5 2 1 2 2 2 3 2 4 2 5

Correct Output: 0 5 5 9 9 12 12 14 14 15

Your Output: 0 5 0 9 0 12 0 14 0 15

One essential condition is that the max cost will never decrease with the increase in capacity. Hope that helps.

1 Like

I think the test case limit on Ck is very loose.
The limit is given upto 109, but the costs can be stored in an int variable!

@eashaaniitkgp this problem can be solved by greedy approach since, the weight in this problem is either 1 or 2. If you have variable weight then you cannot solve this problem by Greedy algorithm.

1 Like

@satya7795, have a look at my answer for some pointers.