首页 > 专题系列 > Java解POJ > POJ 2782 Bin Packing [解题报告] Java
2013
11-12

POJ 2782 Bin Packing [解题报告] Java

Bin Packing

问题描述 :

A set of n 1-dimensional items have to be packed in identical bins. All bins have exactly the same length l and each item i has length li<=l . We look for a minimal number of bins q such that
  • each bin contains at most 2 items,
  • each item is packed in one of the q bins,
  • the sum of the lengths of the items packed in a bin does not exceed l .

You are requested, given the integer values n , l , l1 , …, ln , to compute the optimal number of bins q .

输入:

The first line of the input contains the number of items n (1<=n<=105) . The second line contains one integer that corresponds to the bin length l<=10000 . We then have n lines containing one integer value that represents the length of the items.

输出:

Your program has to write the minimal number of bins required to pack all items.

样例输入:

10
80
70
15
30
35
10
80
20
35
10
30

样例输出:

6

温馨提示:

The sample instance and an optimal solution is shown in the figure below. Items are numbered from 1 to 10 according to the input order.

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int b=in.nextInt();
  ArrayList< Integer> t=new ArrayList< Integer>();
  while((a--)!=0)
	t.add(in.nextInt());
  Collections.sort(t);
  int count=0;
  int u=t.size()-1;
  int k=0;
  while(k<=u)
  {
	int q=b;
	q-=t.get(u--);
	if(q>=t.get(k))
		k++;
	count++;
   }
  System.out.println(count);
 }
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。