Fitting items

[Pen72]

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

[jonnin]

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, ...

[Pen72]

Is this what you mean?

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

[jonnin]

looks Ok. does it work?

[Pen72]

Not really, shows Terminated due to timeout...

[jonnin]

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?

[Pen72]

It shows Terminated due to timeout in 5 cases and successed in 8 cases.

[lastchance]

#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(N²) or O(N² logN) (sorry, struggling to work out which with the erase in as well).

[Pen72]

Hi, your code showed some wrong answers in test cases.

[lastchance]

Mmm, I got N and C muddled up in finding the partition point.

Is this one any better?

#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 

[Pen72]

Yes, it works well now, thanks, I'll dive into the code.