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.
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
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
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
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;
}