KNPSK - Editorial

cook47
easy-medium
greedy
sorting

#1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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:

Author’s solution
Tester’s solution
Editorialist’s solution


#2

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

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


#3

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


#4

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


#5

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


#6

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

thanks


#7

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.


#8

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


#9

For all those who are getting confused about how a greedy strategy worked here:

Actually, if you look carefully, the answer is hidden in the weight values of each object. In the actual knapsack problem, we have to check upon many previous values due to no bound on the weights.

But here, as can be seen, the weight can take only two values, i.e, 1 and 2. Hence, to ascertain the optimal answer for a bag of capacity C, we have to check only two consecutive previous values (because the current total weight i can be achieved only by : (i-1)+1 or (i-2)+2). Hence, only 2 variables storing the previous values are required, hence taking O(1) space, excluding the input storage.


#10

Good day everyone please i would really be glad to know which test case my solution failed on or any error in my code here. I’ve been working on it throughout the night and still getting WA
http://www.codechef.com/viewsolution/4136882


#11

hi…everyone
we can solve this problem simply by dividing the query x<=m by
just assuming x as x=y+2 for y=x-2 which is previously calculated.
for even numbers start with 0. After that start with 2,4,6…as 0+2,2+2,4+2…Now the
answer is highest cost for y and 2, highest cost for y is previously calculated and
for 2 the answer is either cost of 1weight+1weight or 2weight items which have maximum cost
among the remaining. Likewise for odd queries also, starting with 1,1+2,3+2,5+2…
But I am getting WRONG ANSWER …can somebody correct me if i am wrong.
My code as per above idea:http://www.codechef.com/viewplaintext/4137370


#12

what is wrong with my code
http://www.codechef.com/viewsolution/4142521


#13

my O(n long n) solution resulting TLE
http://www.codechef.com/viewsolution/4143667


#14

I am not good at dynamic programming but I wanted to ask if the below given approach is correct or not.
Approach:

Just Sort the W(weight) and C(cost) according to C and then

    for(i=1;i<=sum;i++) {
	ll C = i,j,ans=0;
	for(j=n-1;j>=0;j--) {
		if(C >= (P[j].w)){
			C -= (P[j].w);
			ans += (P[j].c);
		}
	}
	printf("%lld ",ans);
}

Where sum : Total of Weight give i.e value of M

n : N in problem

and P is structure containing Weight (W) and Cost ©

Thank you.


#15

Is this fractional knapsack problem?


#16

Hey can anyone plz tell me why my code is showing a runtime error …whlie it runs perfactly on my local machine…http://www.codechef.com/viewsolution/4177710


#17

hello everyone, I have tried a no. of test cases and my code gives the right answer but I am getting WA on submission. Can anyone plz tell me the test cases where my code is failing…http://www.codechef.com/viewsolution/7476633


#18

whats going wrong in this…:(…???..https://www.codechef.com/viewsolution/9260595


#19

Can somebody please look and tell why i am getting Run-time error for my solution:

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

Thanks in advance.


#20

Hi,

My below code is getting WA.

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

If possible let me know in which test cases it might fail.

The test cases i tried in which it is giving correct answer-
2
1 12
2 1
(op- 12
12
13)

5
2 1
2 2
2 3
2 4
2 5
(op-0
5
5
9
9
12
12
14
14
15)

5
1 1
1 2
1 3
1 4
1 5
(op-5
9
12
14
15)

5
1 34
2 4
1 2
2 0
2 22
(op-34
36
56
58
60
62
62
62)

4
1 4
2 4
1 5
2 5
(op-5
9
10
14
14
18)