Fitting items

Apr 16, 2022 at 7:31am
Is this similar to knapsack problem, what sort of functions should I use?

There are N chocolates and several boxes. Each chocolate has its own calories. Each box can contain at most 2 chocolates and you don't want the total calories of each box to exceed .

Given the calories of each chocolate, please output the minimum required boxes to pack all chocolates.


Input Format

The first line has two integers N and C.

The second line has N integers: the calories of each chocolate.

Sample Input 0

4 10
7 2 3 9
Sample Output 0

3
Apr 16, 2022 at 11:33am
similar in some ways but it is far less difficult due to the additional rules.
you have a starting point .. 1 box per piece.
every time you find a pair that works, you can reduce by 1 and remove that pair.
a simple sort of the data gives NlgN run time + a little more, and there may be a way to avoid the sort even. You do not have to check every combination for every pair.
eg after sorting:
2 3 7 9
try 9 and 2, no, so 9 goes by itself into a box, remove 9.
2 3 7
try 7 and 2, success,
3 remains, box it.
something like that where you take the lowest and highest each time, if its too big, you take the highest alone, if not take both, ...
Last edited on Apr 16, 2022 at 11:36am
Apr 16, 2022 at 1:51pm
Is this what you mean?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set> 
using namespace std;

int main()
{
    int n,c;
    int cnt=0;
    cin>>n>>c;
    multiset<int>A;
    A.clear();
    for(int i=0; i<n ;i++)
    { int x; cin>>x; A.insert(x); }
    
    while(!A.empty())
    {
        if(*prev(A.end()) + *(A.begin()) > c)
       {
           A.erase(prev(A.end()));   
       }
    else
       {
           A.erase(prev(A.end()));
           A.erase(A.begin());  
       }
      cnt++;
    }
    cout<<cnt;
    return 0;
}

Apr 16, 2022 at 3:20pm
looks Ok. does it work?
Apr 17, 2022 at 3:53am
Not really, shows Terminated due to timeout...
Last edited on Apr 17, 2022 at 4:11am
Apr 17, 2022 at 5:27am
Multiset is a little sluggish, but it shouldn't be enough to fail your code.
All that tells me is there must be a O(n) answer, and I don't see it right now.
But, does it actually work? On your test cases, not submitted?
Last edited on Apr 17, 2022 at 5:28am
Apr 17, 2022 at 7:55am
It shows Terminated due to timeout in 5 cases and successed in 8 cases.
Apr 17, 2022 at 11:25am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
   int N, C;
   vector<int> lower, higher;
 
   cin >> N >> C;
// int half = N / 2;           // error
   int half = C / 2;

   for ( int k = 0; k < N; k++ )
   {
      int value;
      cin >> value;
      if ( value <= half ) lower .push_back( value );
      else                 higher.push_back( value );
   }
   sort( lower .begin(), lower .end() );
   sort( higher.begin(), higher.end() );

   int boxes = higher.size();
   if ( higher.size() > lower.size() ) higher.resize( lower.size() );     // Some boxes will be unpairable
   int i = 0, j = higher.size() - 1;
   for ( ; j >= 0; j-- )                                                  // Pair off any higher[] that can
   {
      if ( lower[i] + higher[j] <= C ) i++;
   }
   // Fix what is left over
   if ( i < lower.size() ) boxes += ( 1 + lower.size() - i ) / 2;    // An even number of lower[] can be paired off

   cout << boxes;
}



With your prev(A.end()) being O(N) for any sort of set I suspect your method is either O(N2) or O(N2 logN) (sorry, struggling to work out which with the erase in as well).
Last edited on Apr 17, 2022 at 2:45pm
Apr 17, 2022 at 12:57pm
Hi, your code showed some wrong answers in test cases.
Apr 17, 2022 at 2:46pm
Mmm, I got N and C muddled up in finding the partition point.

Is this one any better?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
   int N, C;
   vector<int> lower, higher;
 
   cin >> N >> C;
   int half = C / 2;

   for ( int k = 0; k < N; k++ )
   {
      int value;
      cin >> value;
      if ( value <= half ) lower .push_back( value );
      else                 higher.push_back( value );
   }
   sort( lower .begin(), lower .end() );
   sort( higher.begin(), higher.end() );

   int boxes = higher.size();
   if ( higher.size() > lower.size() ) higher.resize( lower.size() );     // Some boxes will be unpairable
   int i = 0, j = higher.size() - 1;
   for ( ; j >= 0; j-- )                                                  // Pair off any higher[] that can
   {
      if ( lower[i] + higher[j] <= C ) i++;
   }
   // Fix what is left over
   if ( i < lower.size() ) boxes += ( 1 + lower.size() - i ) / 2;    // An even number of lower[] can be paired off

   cout << boxes;
}


7 10
9 7 2 3 5 1 9
4 
Last edited on Apr 17, 2022 at 3:01pm
Apr 18, 2022 at 8:55am
Yes, it works well now, thanks, I'll dive into the code.
Topic archived. No new replies allowed.