My Blog List

Thursday, December 12, 2013

TOPCORDER SRM598 DIV2 BinPackingEasy

Problem is


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 the int[] 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.

Definition

    
Class: BinPackingEasy
Method: minBins
Parameters: int[]
Returns: int
Method signature: int minBins(int[] item)
(be sure your method is public)

Limits

    
Time limit (s): 2.000
Memory limit (MB): 64

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


and My Code is blow

public static int minBins2(int[] items){
  Arrays.sort(items);
 
  int sp = 0;
  int ep = Math.max(items.length -1, 0);
 
  int totalNum =0; 
  while(true){
   if(items[ep] > 199){
    totalNum ++;
    ep--;
   }else{
    break;
   }
  }
 
  while(ep >= sp){
   if(items[ep] + items[sp] <= 300){
    sp++;
   }
   ep--;
   totalNum++;
  }
 
  return totalNum;
 }


## Access Step ##

1. Sort Items
2. if items are bigger than 199 add totalNum
3. sum of first item and last item are bigger than 300
   last index -- and totalnum ++
.......

i think this is very easy

No comments:

Post a Comment