POJ2782:Bin Packing

时间:2023-02-09 01:31:34

Description

POJ2782:Bin Packing
 

A set of n<tex2html_verbatim_mark> 1-dimensional items have to be packed in identical bins. All bins have exactly the same length l<tex2html_verbatim_mark> and each item i<tex2html_verbatim_mark> has length liPOJ2782:Bin Packingl<tex2html_verbatim_mark> . We look for a minimal number of bins q<tex2html_verbatim_mark> such that

  • each bin contains at most 2 items,
  • each item is packed in one of the q<tex2html_verbatim_mark> bins,
  • the sum of the lengths of the items packed in a bin does not exceed l<tex2html_verbatim_mark> .

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

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of the input file contains the number of items n<tex2html_verbatim_mark>(1POJ2782:Bin PackingnPOJ2782:Bin Packing105)<tex2html_verbatim_mark> . The second line contains one integer that corresponds to the bin length lPOJ2782:Bin Packing10000<tex2html_verbatim_mark> . We then have n<tex2html_verbatim_mark> lines containing one integer value that represents the length of the items.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

For each input file, your program has to write the minimal number of bins required to pack all items.

Sample Input

1

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

Sample Output

6

Note: 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.

POJ2782:Bin Packing
 
将所有物品由大到小排序,从大到小装入物品,如果某个装了一个物品的BIN的余量可以再装入一个物品,就把物品转入,否则就申请一个新的BIN.
 
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int x[];
int main(){
int t;cin>>t;
int g=;
while(t--){
if(g++!=)puts("");
int n;cin>>n;int m;cin>>m;
int sum=;
for(int i=;i<n;i++){
scanf("%d",x+i);
}
sort(x,x+n);
int i=,j=n-;
while(i<j){
if(x[i]+x[j]<=m){
j--;i++;sum++;
}else{j--;sum++;}
}
if(i==j)sum++;
cout<<sum<<endl;
}
return ;
}

POJ2782:Bin Packing的更多相关文章

  1. Bin Packing

    Bin Packing 题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=85904#problem/F 题目: A set of  ...

  2. UVa 102 - Ecological Bin Packing(规律&comma;统计)

    题目来源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&pa ...

  3. UVa - 102 - Ecological Bin Packing

    Background Bin packing, or the placement of objects of certain weights into different bins subject t ...

  4. Vector Bin Packing 华为讲座笔记

    Vector bin packing:first fit / best fit / grasp 成本:性价比 (先验) 设计评价函数: evaluation function:cosine simil ...

  5. UVA 1149 Bin Packing

    传送门 A set of n 1-dimensional items have to be packed in identical bins. All bins have exactly the sa ...

  6. 高效算法——Bin Packing F - 贪心

      Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Submit Status Descripti ...

  7. poj 2782 Bin Packing &lpar;贪心&plus;二分&rpar;

    F - 贪心+ 二分 Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu   Description ...

  8. UVA 1149 Bin Packing 二分&plus;贪心

    A set of n 1-dimensional items have to be packed in identical bins. All bins have exactly the samele ...

  9. UVa 1149 &lpar;贪心&rpar; Bin Packing

    首先对物品按重量从小到大排序排序. 因为每个背包最多装两个物品,所以直觉上是最轻的和最重的放一起最节省空间. 考虑最轻的物品i和最重的物品j,如果ij可以放在一个包里那就放在一起. 否则的话,j只能自 ...

随机推荐

  1. TestLink测试软件安装条件检查不通过的解决方案

    在第一次安装的时候出现这个错误信息 解决办法: 修改config.inc.php文件里的两个属性值为: $tlCfg->log_path = TL_ABS_PATH . 'logs' . DIR ...

  2. android中 EditTex t的 inputType 属性

    //文本类型,多为大写.小写和数字符号    android:inputType="none"    android:inputType="text"    a ...

  3. Linux中vi显示中文乱码的问题

    由于在windows下默认是gb编码,而我的vim默认是utf-8(gedit默认也是utf-8),所以打开会成乱码.修改了一下配置文件,使vi支持gb编码就好了.$vi ~/.vimrclet &a ...

  4. ORACLE CONTROL FILE 笔记

    控制文件包含的信息:   1.数据库的名字   2.联机重做日志文件和数据文件的名字和位置   3.数据库创建的时间戳   4.当前日志的序列号   5.检查点信息   6.备份信息   TIP:数据 ...

  5. Redis 命令 - Sets

    SADD key member [member ...] Add one or more members to a set 127.0.0.1:6379> SADD foo hello (int ...

  6. 从代码都发布遇到的问题总结&lpar;C&num;调用非托管dll文件,部署项目&rpar; 转

    http://www.cnblogs.com/Purple_Xiapei/archive/2012/06/30/2570928.html

  7. css3 display&colon;box

    想做自适应的流体布局 box很有用 . 还没有得到firefox.Opera.chrome浏览器的完全支持,但可以使用它们的私有属性定义firefox(-moz-).opera(-o-).chrome ...

  8. ERROR&colon; gnu-config-native-20150728&plus;gitAUTOINC&plus;b576fa87c1-r0 do&lowbar;unpack&colon; Function failed&colon; Fetcher failure&colon; Fetch command failed with exit code 128&comma; output&colon; fatal&colon; the &&num;39&semi;--set-upstream&&num;39&semi; option is no longer

    /********************************************************************** * ERROR: gnu-config-native-2 ...

  9. centos7和linux防火墙配置入门

    linux部分 iptables -L    列出当前防火墙策略 iptables -F   清空防火墙策略 iptables -P INPUT  DROP   默认设置丢弃进来的流量包(-p指默认策 ...

  10. gitlab常用命令

    进入本地仓库访问位置之后执行命令 1) 远程仓库相关命令 检出仓库:$ git clone git://github.com/jquery/jquery.git 查看远程仓库:$ git remote ...