BinPacking
SRM 598 · 2013-06-25 · by rng_58
SRM 598 · 2013-06-25 · by rng_58 · Brute Force, Greedy
Problem Statement
Problem Statement
Fox Ciel has some items. The weight of the i-th (0-based) item is item[i]. She wants to put all items into bins.
The capacity of each bin is 300. She can put an arbitrary number of items into a single bin, but the total weight of items in a bin must be less than or equal to 300.
You are given theint[] item. It is known that the weight of each item is between 100 and 300, inclusive. Return the minimal number of bins required to store all items.
The capacity of each bin is 300. She can put an arbitrary number of items into a single bin, but the total weight of items in a bin must be less than or equal to 300.
You are given the
Constraints
- item will contain between 1 and 50 elements, inclusive.
- Each element of item will be between 100 and 300, inclusive.
Examples
0)
{150, 150, 150, 150, 150}
Returns: 3
You have five items and each bin can hold at most two of them. You need at least three bins.
1)
{130, 140, 150, 160}
Returns: 2
For example, you can distribute the items in the following way: Bin 1: 130, 150 Bin 2: 140, 160
2)
{100, 100, 100, 100, 100, 100, 100, 100, 100}
Returns: 3
3)
{100, 200, 100, 100, 100, 100, 200, 100, 200}
Returns: 4
4)
{123, 145, 167, 213, 245, 267, 289, 132, 154, 176, 198}
Returns: 8
Submissions are judged against all 132 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BinPacking with a public method int minBins(vector<int> item) · 132 test cases · 2 s / 256 MB per case