$$疊放箱子問題$$

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]來表示第i個箱子到第n個箱子重量為j時箱子的最大數，然后從上往下從后往前一次推過來，最后再從f[1][i](i=0~6000）中選一個最大的即可

動態轉移方程

$$f[i][j]=max\{\begin{array}{ccc}f[i+1][j]& & notselect\\ if((j>=v[i])and(c[i]>=j?v[i]))& f[i+1][j?v[i]]+1& select\end{array}$$

說明：

v為自身重量，c為可承受重量

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,ans,v[1002],c[1002],f[1002][6002]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d",&v[i],&c[i]);memset(f,-127/3,sizeof(f));//初值f[n+1][0]=0;//初值for (int i=n;i>0;i--)for (int j=0;j<=6000;j++){f[i][j]=f[i+1][j];//不放if ((j>=v[i])&&(c[i]>=j-v[i]))//j>=v[i]是為了保證j-v[i]不為負數，c[i]>=j-v[i]是為了保證他可以承受上面的重量f[i][j]=max(f[i][j],f[i+1][j-v[i]]+1);//狀態轉移方程}for (int i=0;i<=6000;i++)ans=max(ans,f[1][i]);//取最大值printf("%d",ans);return 0; }

---

$$方法二$$

用f[i][j]來表示上面的i個箱子選j個箱子的最小值，然后每一層如果不放就直接等于上面的，如果放就要判斷是否能承受上方箱子的重量，再加上當前重量去最小值

動態轉移方程：

$$f[i][j]=min\{\begin{array}{ccc}f[i+1][j]& & notselect\\ if(f[i+1][j?1]<=c[i])& f[i+1][j?1]+v[i]& select\end{array}$$

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,v[1005],c[1005],f[1005][1005],u; int main() {scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d%d",&v[i],&c[i]);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j]=2147483647/3;//初始化u=2147483647/3;f[n][1]=v[n];//初值for (int i=n-1;i>0;--i)//枚舉第i個箱子for (int j=1;j<=n-i+1;++j)//枚舉重量{f[i][j]=f[i+1][j];//不放就繼承上一個的最小重量if (f[i+1][j-1]<=c[i])//判斷是否能承受f[i][j]=min(f[i][j],f[i+1][j-1]+v[i]);//動態轉移方程}for (int i=n;i>=0;--i)if (f[1][i]!=u)//若有變化及可輸出{printf("%d",i);break;//退出，避免重復輸出} }

總結

以上是生活随笔為你收集整理的【动态规划】叠放箱子问题（ssl 1640）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。