题目地址:http://poj.org/problem?id=1742

题目大意

大概意思,有$n$种银币,每种银币分别有$C_i$个。求出能凑出面值$\leq m$的方式个数?

思路

多重部分和问题,首先定义$dp[MAX\_N][MAX\_M]$,$dp[i+1][j]$表示前$i$个银币是否能凑成面值为$j$。

于是有如下递推关系

$$dp[i+1][j] = (0 \leq k \leq m且k \times a_i \leq j时存在dp[i][j-k\times a_i]为真的k)$$

于是得出

/*************************************************************************
    > File Name: 1742.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-02 五 09:25:59 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

int n, m;
int A[102], C[102];
bool dp[102][100005];

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    for(int i=0; i<n; ++i)
        for(int j=0; j<=m; ++j) {
            for(int k=0; k<=C[i] && k*A[i] <= j; ++k)
                dp[i+1][j] |= dp[i][j-k*A[i]]; // 存在k使dp[i][j-k*A[i]]是否为真
        }
    cout << count(dp[n]+1, dp[n]+1+m, true) << endl; // 为真的个数就是能凑成面值<=m的个数
}

int main()
{
#ifdef Oj
    freopen("1742.in", "r", stdin);
#endif
    while(cin >> n >> m) {
        if(n == 0 && m == 0) break;
        for(int i=0; i<n; ++i) cin >> A[i];
        for(int i=0; i<n; ++i) cin >> C[i];
        solve();
    }
    return 0;
}

上面时间复杂度为$O(M \sum_i m_i)$,果断超时。。

继续优化,如果定义$dp[i+1][j]=用前i种数凑成j时最多能剩多少个(无法凑成则为-1)$,则能减少复杂度。

如果前$i-1$个数能凑成$j$的话,第$i$个数就可以留下$C_i$个。此外,前$i$种数凑成$j-A[i]$时第$i$个数还剩下$k(k>0)$的话,那么用这$i$种数凑成$j$时就剩下$k-1$个。由此可得
$$ dp[i+1][j] = \begin{equation} \begin{cases} C_i & (dp[i][j] > 0) \\ -1 & (j < a_i 或 dp[i][j-a_i] \leq 0) \\ dp[i+1][j-a_i] -1 & 其他情况 \end{cases} \end{equation}$$

AC代码

/*************************************************************************
    > File Name: 1742.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-02 五 09:25:59 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

int n, m;
int A[102], C[102];
int dp[100005];

void solve() {
    memset(dp, -1, sizeof(dp));
    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];
            else if(j < A[i] || dp[j-A[i]] <= 0) dp[j] = -1;
            else dp[j] = dp[j-A[i]] - 1;
        }
    }
    // cout << count_if(dp+1, dp + m+1, bind2nd(greater_equal<int>(), 0)) << endl;
    int ans = 0;
    for(int j=1; j<=m; ++j) if(dp[j] >= 0) ++ans;
    cout << ans << endl;
}

int main()
{
#ifdef Oj
    freopen("1742.in", "r", stdin);
#endif
    while(cin >> n >> m) {
        if(n == 0 && m == 0) break;
        for(int i=0; i<n; ++i) cin >> A[i];
        for(int i=0; i<n; ++i) cin >> C[i];
        solve();
    }
    return 0;
}