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.
Can anyone tell me whats wrong with my solution CodeChef: Practical coding for everyone
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: CodeChef: Practical coding for everyone
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
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.
check my answer @eashaaniitkgp