Fitting items

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 (11437)

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

Pen72 (74)

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 (11437)

looks Ok. does it work?

Pen72 (74)

Not really, shows Terminated due to timeout...

Last edited on

jonnin (11437)

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

Pen72 (74)

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

lastchance (6980)

#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).

Last edited on

Pen72 (74)

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

lastchance (6980)

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

Last edited on

Pen72 (74)

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

Topic archived. No new replies allowed.