本题常规的思路是解一个01背包问题。有n个元素可以选，每个元素有一定的容量vi，求不超过一定总容量C的选择方法有多少种。常规的01背包问题的时间复杂度是o(NC)，其中N是元素个数，C是总容量。很明显在这里是会TLE的。
如何降低复杂度呢。有一个巧妙的技巧。考虑到n个元素里可能有重复的，如果只考虑互不相同的元素，那么元素的个数m必然是sqrt(C)的数量级（因为1+2+3+...+m = C）。于是问题转化为：有m种不同元素，每种元素有一定的容量vi和数量ai，求不超过一定总容量C的选择方法有多少种。
我们令dp[i][j]表示前i种元素填装容量j时的方案数目。那么状态转移的关键就是第i种元素我们取几个。可以是0个，1个，2个，直至ai个。于是就有转移方程：
dp[i][j] = dp[i-1][j] + dp[i-1][j-vi] + dp[i-1][j-vi*2] + ... + dp[i-1][j-vi*ai]这个转移方程包括了一个循环，再加上外层两个关于i与j的循环，时间复杂度依然超标。技巧如下。我们分析
dp[i][j-vi] = dp[i-1][j-vi] + dp[i-1][j-vi*2] + dp[i-1][j-vi*3] + ... + dp[i-1][j-vi*(ai+1)]两式相减
dp[i][j] = dp[i][j-vi] + dp[i-1][j] - dp[i-1][j-vi*(ai+1)]我们发现dp[i][j]本身的计算并不需要依赖循环！于是本题的dp解法只需要两层循环即可。注意，以上的表达式里要保证数组下标不是负数，即
dp[i][j] = (j<v?0:dp[i][j-v]) + dp[i-1][j] - (j<v*(c+1)?0:dp[i-1][j-v*(c+1)]);本题另外有一个坑，上面的转移方程中元素的容量v不能为0，否则表达式成了dp[i][j]=dp[i][j]失去了意义。解决办法是将这种元素先踢出去。最终考虑零元素取任何个数都可以。故最终将答案乘以count0+1，其中count0是零元素的个数。