# KNPSK - Editorial

Author: Konstantin Sokol
Tester: Tasnim Imran Sunny
Editorialist: Praveen Dhinwa

EASY-MEDIUM

greedy, sorting

### PROBLEM:

You are given N items, each item has two parameters: the weight and the cost. Let’s denote M as the sum of the weights of all the items.

Your task is to determine the most expensive cost of the knapsack, for every capacity 1, 2, …, M.
The capacity C of a knapsack means that the sum of weights of the chosen items can’t exceed C.

### QUICK EXPLANATION

• ``````  We can greedily start picking the most costliest items with weight <= 2, which can be taken in the knapsack.
``````

### EXPLANATION

For a weight W, can you find the most expensive cost of the knapsack ?

Assume that W is even, we can first select the most expensive items with sum of weights <= 2.
We can do his in following ways.

• ``````  Take the most expensive item of weight 2.
``````
• ``````  Or take the at most two most expensive item of weight 1.
``````

Note that after picking most expensive items with sum of weights <= 2, we will remove the items taken and will recursively
select the items to fill the knapsack with most expensive elements.

Note that if W is odd, then we can simply select the most expensive knapsack of weight 1. Now we won’t consider this item again.
Now we have to select at most W - 1 most expensive weights from the remaining items. Note that W - 1 is even, we can solve this problem
similar to previous problem.

Note that during finding the most expensive cost for the knapsack of weight W, we also find the answer for W - 2. So we can
find answer for all the even W’s in single iteration. We will use another iteration to find answer for odd weights. Please
view the pseudo code to understand more about it.

Pseudo code

``````	// Let "one" denote the array with items with weight 1 sorted in increasing order of cost.
// Let "two" denote the array with items with weight 2 sorted in increasing order of cost.

// First we will construct answer for weights being even.
long long cur = 0;
// iterate over even weights.
// let ans[w] be the answer for the weight w.
for (int w = 2; w <= W; w += 2) {
// pick the most expensive atmost 2 elements and take those items into knapsack.
// let their sum of their costs be cost.
cur += cost;
ans[w] = cur;
}

// Now we will construct answer for weights being odd.
long long cur = 0;
// iterate over odd weights.
// let ans[w] be the answer for the weight w.
if (one.size() >= 1) {
// pick the highest weighed item with weight = 1.
cur = one[one.size() - 1];
one.remove(one.size() - 1);
ans[1] = cur;
}
for (int w = 3; w <= W; w += 2) {
// pick the most expensive atmost 2 elements and take those items into knapsack.
// let their sum of their costs be cost.
cur += cost;
ans[w] = cur;
}
``````

Complexity
N log N, as we are only doing sorting of two arrays of size at most N.

For a reference implementation, please refer to editorialist’s solution.

### AUTHOR’S AND TESTER’S SOLUTIONS:

14 Likes

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

I used a similar approach but could not get an AC. Can someone help me find my mistake ?

http://www.codechef.com/viewsolution/4132306

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.

I tried every test case…but can’t find the mistake in my code…pls help!!
http://www.codechef.com/viewsolution/4132127

1 Like

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 ^.^

8 Likes

We can use priority queue and solve it in single iteration, covering both odd and even value for W.
http://www.codechef.com/viewsolution/4132064

I used simple approach what is the reason for runtime error in my code… pls help me http://www.codechef.com/viewsolution/4133591

@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.

can somebody please tell why i am getting a wa.
http://www.codechef.com/viewsolution/4133943

thanks

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

This was a really twisted question…

I saw the link http://en.wikipedia.org/wiki/Knapsack_problem and it clearly mentions that this problem cannot be solved by greedy algorithm and the optimum answer is derived from the DP algorithm.

I still don’t exactly understand how greedy works for this question. Can someone please properly explain.

Can someone please tell me where does my code fail?
http://www.codechef.com/viewsolution/4135045