【动态规划】叠放箱子问题（ssl 1640） |
您所在的位置：网站首页 › 集装箱承受重量 › 【动态规划】叠放箱子问题（ssl 1640） |
【动态规划】叠放箱子问题（ssl 1640）
|
叠 放 箱 子 问 题 叠放箱子问题 叠放箱子问题
Description
某港口有一批集装箱，将其编号，分别为1至N。每一个箱子的外型尺寸都是一样的，现在要将其中某些集装箱叠放起来，集装箱叠放的规则如下：
1)每个集装箱上最多只能直接叠放一个集装箱。
2)编号较小的集装箱不能放在编号较大的集装箱之上。
3)每个集装箱都给出了自身的重量和可承受的重量，每个集装箱之上的所有集装箱重量之和不得超过该集装箱的可承受的重量。
现在要求你编程，从中选出最多个集装箱，使之在满足以上条件的情况下叠放起来，即要求叠得尽可能地高。
Input
第一行是一个正整数N，表示共有N个集装箱（1≤ N ≤1000）。
以下共有N行，每行两个正整数，中间用空格分隔，分别表示每个集装箱的自身重量和可承受的重量，两个数均为小于等于3000。
Output
输出最多可叠放的集装箱总数。运行时间不超过去时10秒。
Sample Input
5
19 15
7 13
5 7
6 8
1 2
Sample Output
４
题目大意：
有n个箱子，每个箱子都有自己的编号，自身重量，可承受重量（输入第i+1行是编号为i的箱子自身重量和可承受重量)，编号小的必须在编号大的下面，箱子上面只能直接放一个箱子，但上面的这个箱子上面还可以放箱子（例如下图是合法的），求最多可叠放多少个箱子
f [ i ] [ j ] = m a x { f [ i + 1 ] [ j ] n o t s e l e c t i f ( ( j ; = v [ i ] ) a n d ( c [ i ] ; = j − v [ i ] ) ) f [ i + 1 ] [ j − v [ i ] ] + 1 s e l e c t f[i][j]=max\left\{\begin{matrix} f[i+1][j];;not select \\ if ((j;=v[i])and(c[i];=j-v[i]));f[i+1][j-v[i]]+1;select \end{matrix}\right. f[i][j]=m |
【本文地址】
今日新闻 |
推荐新闻 |