免费空间申请网站,郑州360房产网查询,网站分几种类型,杭州 商城网站开发叠放箱子问题叠放箱子问题叠放箱子问题
Description
某港口有一批集装箱#xff0c;将其编号#xff0c;分别为1至N。每一个箱子的外型尺寸都是一样的#xff0c;现在要将其中某些集装箱叠放起来#xff0c;集装箱叠放的规则如下#xff1a;
1)每个集装箱上最多只能直接…叠放箱子问题叠放箱子问题叠放箱子问题
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个箱子每个箱子都有自己的编号自身重量可承受重量输入第i1行是编号为i的箱子自身重量和可承受重量)编号小的必须在编号大的下面箱子上面只能直接放一个箱子但上面的这个箱子上面还可以放箱子例如下图是合法的求最多可叠放多少个箱子 方法一方法一方法一
用一个二维数组f[i][j]来表示第i个箱子到第n个箱子重量为j时箱子的最大数然后从上往下从后往前一次推过来最后再从f[1][i](i0~6000中选一个最大的即可
动态转移方程
f[i][j]max{f[i1][j]notselectif((jgt;v[i])and(c[i]gt;j−v[i]))f[i1][j−v[i]]1selectf[i][j]max\left\{\begin{matrix} f[i1][j]amp;amp;not select \\ if ((jgt;v[i])and(c[i]gt;j-v[i]))amp;f[i1][j-v[i]]1amp;select \end{matrix}\right.f[i][j]max{f[i1][j]if((jv[i])and(c[i]j−v[i]))f[i1][j−v[i]]1notselectselect
说明
v为自身重量c为可承受重量
#includecstdio
#includeiostream
#includecstring
using namespace std;
int n,ans,v[1002],c[1002],f[1002][6002];
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d%d,v[i],c[i]);memset(f,-127/3,sizeof(f));//初值f[n1][0]0;//初值for (int in;i0;i--)for (int j0;j6000;j){f[i][j]f[i1][j];//不放if ((jv[i])(c[i]j-v[i]))//jv[i]是为了保证j-v[i]不为负数c[i]j-v[i]是为了保证他可以承受上面的重量f[i][j]max(f[i][j],f[i1][j-v[i]]1);//状态转移方程}for (int i0;i6000;i)ansmax(ans,f[1][i]);//取最大值printf(%d,ans);return 0;
}方法二方法二方法二
用f[i][j]来表示上面的i个箱子选j个箱子的最小值然后每一层如果不放就直接等于上面的如果放就要判断是否能承受上方箱子的重量再加上当前重量去最小值
动态转移方程
f[i][j]min{f[i1][j]notselectif(f[i1][j−1]lt;c[i])f[i1][j−1]v[i]selectf[i][j]min\left\{\begin{matrix} f[i1][j]amp;amp;not select \\ if (f[i1][j-1]lt;c[i])amp;f[i1][j-1]v[i]amp;select \end{matrix}\right.f[i][j]min{f[i1][j]if(f[i1][j−1]c[i])f[i1][j−1]v[i]notselectselect
#includecstdio
#includeiostream
#includecstring
using namespace std;
int n,v[1005],c[1005],f[1005][1005],u;
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d%d,v[i],c[i]);for(int i1;in;i)for(int j1;jn;j)f[i][j]2147483647/3;//初始化u2147483647/3;f[n][1]v[n];//初值for (int in-1;i0;--i)//枚举第i个箱子for (int j1;jn-i1;j)//枚举重量{f[i][j]f[i1][j];//不放就继承上一个的最小重量if (f[i1][j-1]c[i])//判断是否能承受f[i][j]min(f[i][j],f[i1][j-1]v[i]);//动态转移方程}for (int in;i0;--i)if (f[1][i]!u)//若有变化及可输出{printf(%d,i);break;//退出避免重复输出}
}
