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
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.
Is this fractional knapsack problem?
Hey can anyone plz tell me why my code is showing a runtime error …whlie it runs perfactly on my local machine…CodeChef: Practical coding for everyone
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…CodeChef: Practical coding for everyone
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.
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)
2 Likes
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.
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.