叠放箱子问题（方法一）【DP】

> Description 有一堆十分之麻烦的箱子需要你帮忙竖着叠放： 1.编号小的箱子必须放在编号大的之下； 2.每个箱子上面只能放一个箱子； 3.每个箱子都有它的自身重量和承受重量，必须保证这个箱子之上所有箱子的重量不超过这个箱子的承受重量。

更麻烦的是，还要你算出n个箱子按照这样的方式来叠放，最多可以叠放多少个箱子。

> Input 第一行输入箱子数n（1≤ N ≤1000）。 接下来n行分别输入第i个箱子的自身重量和承受重量，两个数均为小于等于3000。

> Output 输出最多的箱子数

> Sample Input 5 19 15 7 13 5 7 6 8 1 2

> Sample Output 4

> 解题思路 按照老师的话来说这一道题十分考验智商。。。 这一道题用DP来解。 因为这个箱子很让人秃头，又要按顺序又要保证不超过承受重量的，所以这个方法是从上往下看的，就是f[i][j]表示的是从i到n这些箱子中总重量为j的最优值，它按照这个思维排箱子也不是从下往上垒的，而是从上往下的（我理解为它是在半空中排箱子）。

然后算的时候就有些像背包了 说明背包真的很重要 ， 状态转移方程（要么选要么不选）：

f[i][j]=max(f[i+1][j],f[i+1][j-w[i]]+1)

i+1因为是从上往下的，所以之前一个阶段应该是在i+1这里；j-w[i]是因为j是总重量，要选择第i个箱子拍下去就应该空出位置给它。

判断：j>=w[i]防止算出负数，越界 　　　c[i]>=j-w[i]按照题目描述那样，必须上面的总重量必须小于等于承受重量，j为总重量，再减去这个箱子的重量就等于上面箱子的重量。

> 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,c[1005],w[1005],f[1005][6005]={
          
   0};
int main()
{
          
   
    int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
	for(int i=n;i>=1;i--)
	 for(int j=1;j<=6000;j++)
	  //6000是因为箱子自身重量和承受重量分别最多为3000，而j为它们的总重量
	 {
          
   
	 	if(j>=w[i]&&c[i]>=j-w[i]) //判断
	 	 f[i][j]=max(f[i+1][j],f[i+1][j-w[i]]+1);
	 	 //+1——增加一个箱子
	 	else f[i][j]=f[i+1][j]; //不然就不选
	 }
	for(int i=1;i<=6000;i++)
	 ans=max(ans,f[1][i]);
	//最多箱子数的总重量是不定的，所以要循环判断一下
	printf("%d",ans);
	return 0;
}