### 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
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
Is this what you mean?

 ``12345678910111213141516171819202122232425262728293031323334`` ``````#include #include #include #include #include #include using namespace std; int main() { int n,c; int cnt=0; cin>>n>>c; multisetA; A.clear(); for(int i=0; i>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<

looks Ok. does it work?
Not really, shows Terminated due to timeout...
Last edited on
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
It shows Terminated due to timeout in 5 cases and successed in 8 cases.
 ``123456789101112131415161718192021222324252627282930313233343536`` ``````#include #include #include using namespace std; int main() { int N, C; vector 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
Hi, your code showed some wrong answers in test cases.
Mmm, I got N and C muddled up in finding the partition point.

Is this one any better?
 ``1234567891011121314151617181920212223242526272829303132333435`` ``````#include #include #include using namespace std; int main() { int N, C; vector 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
Yes, it works well now, thanks, I'll dive into the code.
Topic archived. No new replies allowed.