Simone
本题为明显的唱片制作问题的另一种说法：
方程：f[i,j,k]表示前I个物品放入前J个背包，外加k的容量时的最大值。F[i,j,k]=max(f[i-1,j,k],f[i-1,j,k-w[i]]+1](w[i]<=k）；
F[i,j,k]:=max(f[i-1,j,k],f[i-1,j-1,t-w[i]](w[i]>k)；
我对楼上的回答深表怀疑！
变异版0-1背包，先w[i]排序，再针对每个背包回溯或者动态规划，最后统计了事……
f[n,m]:=f[n-1,m]*m+f[n-1,m-1];
请参考
表示赞成LS，LS做法正确，只是这题还有O(N^2)的算法
改进的状态表示描述为：
g[i,j]=(a, b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i件武器中选取j件所需的最少背包为：a个背包另加b容量。
状态转移方程为：
g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}
其中(a, b)+long[i]=(a’, b’)的计算方法为：
当b+long[i] ≤t时： a’=a; b’=b+long[i];
当b+long[i] ＞t时： a’=a+1; b’=long[i];
规划的边界条件：
当0≤i≤n时，g[i,0]=(0,0)
题目所求的最大值是：answer=max{k| g[n, k]≤(m-1,t)}
可用f[i,j]=a,g[i,j]=b来做
详见：动态规划算法的优化技巧---2001毛子青论文
