BinPackingEasy
SRM 598 · 2013-06-25 · by rng_58
SRM 598 · 2013-06-25 · by rng_58 · 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 101 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 101 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)
{101, 101, 101, 101, 101, 101, 101, 101, 101}
Returns: 5
3)
{101, 200, 101, 101, 101, 101, 200, 101, 200}
Returns: 6
4)
{123, 145, 167, 213, 245, 267, 289, 132, 154, 176, 198}
Returns: 8
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BinPackingEasy with a public method int minBins(vector<int> item) · 67 test cases · 2 s / 256 MB per case