多重部分和问题（dp）

题目：POJ1742

大意：有n种不同大小的硬币，面值是a_i每种有m_i个，题目问，这些硬币能够在价格1-m之间，付款多少种金额？

这个问题就是dp的多重部分和问题，在定义递推关系的时候，不同的递推关系会影响到复杂度。

下面是TLE的思路：

dp[i+1][j]=前i种数字能否加成j

那么，递推关系就是dp[i+1][j]=(0<=k<=m_i且k*a_i<=j时存在使dp[i][j-k*a_i]为真的k) 其实这就是把他们 或 起来

然而这个算法的复杂度是O(KΣ_im_i)，于是在题目要求下，就tle了

下面是MLE的思路

如果我们不仅求出是否能加和得到目标数值，还顺便把得到这个数的时候，a_i还剩下多少个也算出来，那么就可以降低时间复杂度。

把dp数组改为：

dp[i+1][j]=用前i种数，加和得到j时，第i种数最多还能剩下多少个。

按照上面的递推关系，写出转移方程：

1. dp[i+1][j]= m_i (dp[i][j]>=0) 就是说，当前i-1种数已经可以加和为j了，那么第i种数就不需要加了，最多还能剩下m_i个。
2. dp[i+1][j] = -1 (当不属于上面的情况时，若j<a_i或者dp[i+1][j-a_i]<=0) 也就是说，当j比第i种数的大小还小的话，就没法通过加上a_i得到j，因此设置为-1.并且，当j-a_i小于等于0的时候，说明当前数已经用完了，没法加到j了。
3. 除了上面两种情况以外，则dp[i+1][j]=dp[i+1][j-a_i]-1 也就是从前i种数加到j-a_i转移而来。

上面这个思路是正确的，但是我们需要开一个很大的二维数组，对于这一题来说，就MLE了

重复利用数组，降低空间复杂度

我们会发现，当我们进行循环时，是按照i，一位一位进行增加的，在计算第i位的时候，i-1位之前的数据其实已经不需要了。我们新生成的第i位的数据仅仅是由第i-1位转移而来的，并且，一旦完成转移，第i-1位的数据也不再需要了。这样的话，我们可以只用一个数组来记录。

因此，AC代码如下：

#include <iostream>
using namespace std;
#define MAXN 105
#define MAXM 100005
struct coin
{
    int val, num;
} c[MAXN];
int n, m;

int dp[MAXM]; //前i种硬币，加到j元时，第i种剩余的最大值

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (1)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;

        for (int i = 0; i < n; ++i)
        {
            cin >> c[i].val;
        }
        for (int i = 0; i < n; ++i)
        {
            cin >> c[i].num;
        }

        for (int i = 0; i <= m + 1; ++i)
        {

            dp[i] = -1;
        }
        dp[0] = 0;


        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j <= m; ++j)
            {
                if (dp[j] >= 0)
                    dp[j] = c[i].num; //前i-1种硬币已经能加到j元
                else if (j < c[i].val || dp[j - c[i].val] <= 0)
                {
                    //前i种硬币无法加到j元
                    dp[j] = -1;
                }
                else
                {
                    dp[j] = dp[j - c[i].val] - 1;
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= m; ++i)
        {
            if (dp[i] >= 0)
                ++ans;
        }
        cout << ans << endl;
    }
    return 0;
}

转载请注明来源：https://www.longjin666.top/?p=1099

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~