题目大意：
购物，买相应物品之前必须先买能装相应物品的盒子，现在已知n个盒子的价钱，以及每个盒子能装的物品数，以及这些物品的价值和花费。为ｗ钱下能买到物品的最大价值。
思路：背包。首先很容易想到的一个状态转移方程是：
ＤＰ［ｉ］［ｊ］＝ＭＡＸ{ＤＰ［ｉ－１］［ｊ］，ＭＡＸ{ＤＰ［ｉ－１］［ｊ－ｋ］＋Ｐａｃｋ［ｉ］［ｋ］}}。其中
ＤＰ［ｉ］［ｊ］表示前ｉ个盒子中，在金钱ｊ下所能得到的最大价值。考虑第ｉ个盒子选和不选，以及选的话分配多少钱给ｉ。
然而很明显上述时间复杂度过高。考虑优化。仔细分析，会发现ＭＡＸ{ＤＰ［ｉ－１］［ｊ－ｋ］＋Ｐａｃｋ［ｉ］［ｋ］}，
实际上表示的是在金钱ｊ下且一定考虑第ｉ个盒子下的最大价值。将盒子的价值看作０，在金钱ｊ下首先将盒子的价钱考虑进去。那么剩下的只是挑选ｉ盒子中的物品，即０１背包。令ｆ（ｉ，ｊ）为前ｉ个盒子中且第ｉ个盒子必须考虑时在金钱ｊ下的
所得最大价值。那么该初始值ｆ（ｉ，ｊ）＝ＤＰ［ｉ－１］［ｊ－Ｐｂｏｘ［ｉ］］＋０；初始值确定以后（相当于已经忽略了盒子的影响）。那么直接背包即可。
——————转载
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define M 100001 int dp[51][M],n; int main() { int n,v; while(scanf("%d%d",&n,&v)!=EOF){ memset(dp,-1,sizeof dp); memset(dp[0],sizeof dp[0]); for(int i=1;i<=n;++i){ int x,p; scanf("%d%d",&x,&p); for(int j=x;j<=v;++j) dp[i][j]=dp[i-1][j-x]; while(p--){ int c,w; scanf("%d%d",&c,&w); for(int j=v;j>=c;--j){ if(dp[i][j-c]!=-1){ dp[i][j]=max(dp[i][j],dp[i][j-c]+w); } } } for(int j=0;j<=v;++j){ dp[i][j]=max(dp[i][j],dp[i-1][j]); } } cout<<dp[n][v]<<endl; } return 0; }
