平均值问题

Published: October 04, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 动态规划相关

动态规划相关

题目1：现在有重量为$1,2,\ldots,n$的商品各$k$件，希望取走一部分商品，要求对所有$1\leq x\leq n$计算有多少种取法（不允许一个不取），取走的商品的平均重量恰好为$x$。这里满足$1\leq n,k\leq 100$。

对于平均值的计算方法，普通的思路就是算出总和，之后除去总数的到。于是这给出了一个DP，时间复杂度为$O(n^4k^2)$，太慢了。

还有一种计算平均值的方案，即先将所有的商品重量都减去$x$，之后如果商品的总重量正好等于$0$，那么平均值就一定是$x$。这种方法的好处就可以允许我们的DP数组不用再记录具体取了多少件商品。

现在的解决方案就非常简单了，记$dp(i,j)$表示重量为$1$到$i$的货物的总重量为$j$的方案数。这个dp的时间复杂度为$O(n^3k)$，还是可以接受的。

接下来要计算平均值为$x$的方案数，其结果为$dp(x-1,0)dp(n-x,0)k+\sum_{i>0}dp(x-1,i)dp(n-x,i)(k+1)$。

提供一道题目。