POJ 1742 - Coins

http://poj.org/problem?id=1742

Description

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins. 

Input

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

Sample Output

8
4

http://www.hankcs.com/program/cpp/poj-1742-coins.html
传说中的男人八题，是男人就A这八题。有n种面额的硬币，面额个数分别为A_i、C_i，求最多能搭配出几种不超过m的金额？
poj 1742 Coins(多重背包)

给定n种面值的硬币面值分别为wi个数为ci，问用这些硬币可以组成1~m之间的多少面值
解题思路：楼教主的男人八题之一，算是一个经典的问题，定义一个sum数组。每次填dp[j]时直接由dp[j-weight[i]]推出，
          前提是sum[j-w[i]]<c[i].sum每填一行都要清零，sum[j]表示当前物品填充j大小的包需要至少使用多少个.复杂度O(n*m)

这是一个多重部分和问题(多重背包问题)，放在了《2.3 记录结果再利用的“动态规划” 优化递推关系式》。最基本的做法是：

dp[i][j] := 用前i种硬币能否凑成j

递推关系式：

dp[i][j] = （存在k使得dp[i – 1][j – k * A[i]]为真，0 <= k <= m 且下标合法）

然后三重循环ijk递推

http://blog.csdn.net/u014688145/article/details/71136194

该dp很有意思，用boolean[][] dp，具有传递效果。递推式：

dp[i+1][j] |= dp[i][j-k*A[i]];

1


1

最后统计dp[n][1]~dp[n][m]中有多少个true即可。

public static void main(String[] args) { Scanner in = new Scanner(System.in); while (true){ int n = in.nextInt(); int m = in.nextInt(); if (n == 0 && m == 0) break; int[] A = new int[n]; int[] C = new int[n]; for (int i = 0; i < n; i++){ A[i] = in.nextInt(); } for (int i = 0; i < n; i++){ C[i] = in.nextInt(); } boolean[][] dp = new boolean[n+1][m+1]; 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++){ if (k * A[i] <= j){ dp[i+1][j] |= dp[i][j-k*A[i]]; } } } } int count = 0; for (int i = 1; i <= m; i++){ if (dp[n][i]) count ++; } System.out.println(count); } in.close(); } }

很遗憾，TLE，更新可视图如下：

上述情况不算if条件的过滤，时间复杂度为O(n∑i(m∗ki))，看下图：

如当i = 0, j = 3时，它也会有三次伪更新，但这三次更新是否有必要？显然完全不需要，因为我们知道dp[0][3] = 0。所以，程序很明显会TLE。

这里的主要原因在于，我们在计算下一阶段状态时，丢失了一些非常关键的信息。试想一下，我们能否在下一阶段带上前一阶段的硬币数？

观察上述更新过程，你会发现，它的更新很有特点，如从阶段0 -> 阶段1，有三次有效更新，而三次正是硬币可选择的个数0,1,2。同理，阶段1 -> 阶段2，两次有效更新，而硬币选择的个数为0,1。所以，给了我们一个启发，把硬币个数带入下一阶段，然后让它平行更新

所以有了新的递推式：

dp[i][j] = c[i] // 表示当前能够更新的最大可能数。 dp[i][j] = -1 // 表示当前无法再更新 更新规则： // 上一阶段跳入下一阶段 dp[i+1][j] = C[i], if dp[i][j] >= 0 // 说明当前面值可以在下一阶段递增 // 越界（当前面值超过最大数m）或者当前阶段没有硬币可用 dp[i+1][j] = -1, if j < A[i] || dp[i+1][j-A[i]] <= 0 // 用掉一个硬币，递推式减1，直到-1 dp[i+1][j] = dp[i+1][j-A[i]] - 1;
public static int solve(int n, int m, int[] A, int[] C){ int[][] dp = new int[n+1][m+1]; for (int i = 0; i < dp.length; i++){ Arrays.fill(dp[i], -1); } dp[0][0] = 0; for (int i = 0; i < n; i++){ for (int j = 0; j <= m; j++){ if (dp[i][j] >= 0){ dp[i+1][j] = C[i]; } else if (j < A[i] || dp[i+1][j - A[i]] <= 0){ dp[i+1][j] = -1; } else{ dp[i+1][j] = dp[i+1][j-A[i]] - 1; } } } int answer = 0; for (int i = 1; i <= m; i++){ if (dp[n][i] >= 0) answer++; } return answer; }

我们再来看看它的更新图，如下：

呵呵，MLE了，真是题目虐我千百遍，我待她如初恋啊，书上也说了，有些题就得重复利用数组。为啥可以？看上图，平行更新，且由if判断的顺序决定。

    public static int solve(int n, int m, int[] A, int[] C){
        int[] dp = new int[m+1];
        Arrays.fill(dp, -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];
                }
                else if (j < A[i] || dp[j-A[i]] <= 0){
                    dp[j] = -1;
                }
                else{
                    dp[j] = dp[j-A[i]] - 1;
                }
            }
        }

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

http://www.hankcs.com/program/cpp/poj-1742-coins.html

这个算法每次只记录一个bool值，损失了不少信息。在这个问题中，不光能够求出是否能得到某个金额，同时还能把得出了此金额时A_i还剩下多少个算出来，这样直接省掉了k那重循环。

优化dp定义：

dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来）
            如果dp[i - 1][j] >= 0(前i-1个数可以凑出j，那么第i个数根本用不着)直接为C[i]
dp[i][j] =  如果j < A[i]或者dp[i][j - a[i]] <=0 (面额太大或者在配更小的数的时候就用光了）-1
            其他（将第i个数用掉一个） dp[i][j-a[i]] - 1

http://www.cnblogs.com/E-star/archive/2011/12/08/2280973.html

    while(scanf("%d%d",&n,&V),n+V)
    {
        int ans=0;
        for(i=0;i<n;i++)
        scanf("%d",&w[i]);
        for(i=0;i<n;i++)
        scanf("%d",&b[i]);
        for(i=f[0]=1;i<=V;i++) f[i]=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<=V;j++) sum[j]=0;//关键是用sum来限定了次数
            for(j=w[i];j<=V;j++)//从w[i]到V循环检查看是否能够出现前边没有出现的价格
            {
                if(!f[j]&&f[j-w[i]]&&sum[j-w[i]]<b[i])
                //如果j价格没有出现过，且j-w[i]出现过，并且使用i硬币的次数没有超出给定的数量
                {
                    f[j]=1;//标记为已出现过
                    sum[j]=sum[j-w[i]]+1;//使用次数+1
                    ans++;//满足条件++
                }
            }
        }
        cout<<ans<<endl;
    }

X. http://blog.csdn.net/xiaozhuaixifu/article/details/10911619
这个会超时

1.     while(cin>>N>>M)  
2.     {  
3.         if(N+M==0)break;  
4.         for(int i=0;i<N;i++) cin>>val[i];  
5.         for(int i=0;i<N;i++) cin>>num[i];  
6.         for(int i=0;i<=M;i++) dp[i]=0;  
7.         dp[0]=1;  
8.         for(int i=0;i<N;i++){  
9.             for(int j=M;j>=1;j--){  
10.                 for(int k=0;k<=num[i]&&k*val[i]<=j;k++){  
11.                     dp[j] |= dp[j-k*val[i]];  
12.                 }  
13.             }  
14.         }  
15.         int ans=0;  
16.         for(int i=1;i<=M;i++) if(dp[i]) ans++;  
17.         cout<<ans<<endl;  
18.     } 

X. POJ 1742 -- Coins

1. int main()
2. {
3. int i, cnt;
4.  
5. for(i=0; i<1024; i++) w[i] = 1;
6. while(scanf("%d%d", &N, &V) && (N || V)) {
7. cnt = 0;
8. for(i=0; i<N; i++) scanf("%d", &c[i]);
9. for(i=0; i<N; i++) scanf("%d", &m[i]);
10. for(i=0; i<V+1; i++) f[i] = -INF;
11.  
12. f[0] = 0;
13. for(i=0; i<N; i++) {
14. mul_pack(f, c[i], w[i], m[i]);
15. }
16. for(i=1; i<=V; i++) if(f[i]>=0) cnt++;
17. printf("%d\n", cnt);
18. }
19.  
20. return 0;
21. }
22.  
23. void zo_pack(int f[], int c, int w)
24. {
25. for(int i=V; i>=c; i--) {
26. if(f[i-c]+w>f[i]) f[i] = f[i-c]+w;
27. }
28. }
29.  
30. void com_pack(int f[], int c, int w)
31. {
32. for(int i=c; i<=V; i++) {
33. if(f[i-c]+w>f[i]) f[i] = f[i-c]+w;
34. }
35. }
36.  
37. void mul_pack(int f[], int c, int w, int m)
38. {
39. if(c*m>V) {
40. com_pack(f, c, w);
41. return ;
42. }
43. for(int k=1; k<m; ) {
44. zo_pack(f, k*c, k*w);
45. m = m-k;
46. k *= 2;
47. }
48. zo_pack(f, c*m, w*m);
49. }

这是一个多重部分和问题(多重背包问题)，放在了《2.3 记录结果再利用的“动态规划” 优化递推关系式》。

dp[i][j] := 用前i种硬币能否凑成j
递推关系式：
dp[i][j] = （存在k使得dp[i - 1][j - k * A[i]]为真，0 <= k <= m 且下标合法）
然后三重循环ijk递推

bool dp[100 + 16][100000 + 16]; // dp[i][j] := 用前i种硬币能否凑成j

int A[100 + 16];

int C[100 + 16];

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int n, m;

    while(cin >> n >> m && n > 0)

    {

        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < n; ++i)

        {

            cin >> A[i];

        }

        for (int i = 0; i < n; ++i)

        {

            cin >> C[i];

        }

        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]];

                }

            }

        }

        int answer = count(dp[n] + 1, dp[n] + 1 + m , true); // 总额0不算在答案内

        cout << answer << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

这种代码不用提交也知道会TLE，因为这个朴素的算法的复杂度是O(m∑iCi)，比如那第二个用例画成图的话会看到：

这个算法每次只记录一个bool值，损失了不少信息。在这个问题中，不光能够求出是否能得到某个金额，同时还能把得出了此金额时A_i还剩下多少个算出来，这样直接省掉了k那重循环。

优化dp定义：

1 2 3 4

dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来）             如果dp[i - 1][j] >= 0(前i-1个数可以凑出j，那么第i个数根本用不着)直接为C[i] dp[i][j] =  如果j < A[i]或者dp[i][j - a[i]] <=0 (面额太大或者在配更小的数的时候就用光了）-1             其他（将第i个数用掉一个） dp[i][j-a[i]] - 1

最后统计一下dp数组第n行>=0的个数就知道答案了：

还是拿第二个用例画个图：

int dp[100 + 16][100000 + 16]; // dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个

int A[100 + 16];

int C[100 + 16];

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int n, m;

    while(cin >> n >> m && n > 0)

    {

        memset(dp, -1, sizeof(dp));

        dp[0][0] = 0;

        for (int i = 0; i < n; ++i)

        {

            cin >> A[i];

        }

        for (int i = 0; i < n; ++i)

        {

            cin >> C[i];

        }

        for (int i = 0; i < n; ++i)

        {

            for (int j = 0; j <= m; ++j)

            {

                if (dp[i][j] >= 0)

                {

                    dp[i + 1][j] = C[i];

                }

                else if (j < A[i]                        // 用一个就超出，不能用

                        || dp[i + 1][j - A[i]] <= 0)      // 连凑比j小的数的时候都用完了，此时更加用完了

                {

                    dp[i + 1][j] = -1;

                }

                else

                {

                    dp[i + 1][j] = dp[i + 1][j - A[i]] - 1;       // 用上了一个第i个硬币

                }

            }

        }

        int answer = count_if(dp[n] + 1, dp[n] + 1 + m , bind2nd(greater_equal<int>(), 0)); // 总额0不算在答案内

        cout << answer << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

本以为这次照着书上的思路来的应该没问题了吧，数组再利用就懒得做了。于是提交，结果MLE.

于是打起精神来重复利用数组，注意到上图中的箭头都是垂直的，也就是说可以定义

dp[j] := 在第i次循环时之前表示用前i-1种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来），循环之后就表示第i次的状态

于是就省了一维数组：

int dp[100000 + 16]; // dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个

int A[100 + 16];

int C[100 + 16];

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int n, m;

    while(cin >> n >> m && n > 0)

    {

        memset(dp, -1, sizeof(dp));

        dp[0] = 0;

        for (int i = 0; i < n; ++i)

        {

            cin >> A[i];

        }

        for (int i = 0; i < n; ++i)

        {

            cin >> C[i];

        }

        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)       // 连凑比j小的数的时候都用完了，此时更加用完了

                {

                    dp[j] = -1;

                }

                else

                {

                    dp[j] = dp[j - A[i]] - 1;     // 用上了一个第i个硬币

                }

            }

        }

        int answer = count_if(dp + 1, dp + 1 + m , bind2nd(greater_equal<int>(), 0)); // 总额0不算在答案内

        cout << answer << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

X. DP 2
https://gist.github.com/amoshyc/c8bf4ce80ba6facdbb83

原始想法會 TLE，時間複雜度為 O(N * M * max(C[i]))：

bool dp[i][w] = 使用前 i 個硬幣可不可以組出 w
dp[i][w] = any([dp[i-1][w - k * a[i]] for 0 <= k <= C[i]])
dp[0][0] = true

優化的方法為當成 無限背包 來做，但另外記錄硬幣的使用個數。

###定義

bool dp[w] = 可不可以組出 w
int num[w] = 組出 w 需使用幾個 A[i] 硬幣

答案為 count(dp + 1, dp + M + 1, true)

剩下的直接寫在程式碼的注釋裡。時間複雜度降到 O(N*M)

int solve() {
    memset(dp, false, sizeof(dp));

    dp[0] = true;
    for (int i = 0; i < N; i++) {
        // num[j] 記錄組出 j 需使用幾個 **A[i]** 硬幣。
        memset(num, 0, sizeof(num));
        
        // j 從 A[i] 開始，當然。比 A[i] 小的，不可能用 A[i] 組出。
        for (int j = A[i]; j <= M; j++) {
            // 如果 j 尚無法組出，
            // 且 j - A[i] 可以組出，且硬幣數量沒有超過（至少還有一枚可以用）
            if (dp[j] == false && dp[j - A[i]] && num[j - A[i]] < C[i]) {
                dp[j] = true; // j 就可以組出
                num[j] = num[j - A[i]] + 1;
                // 組出 j 的硬幣數量為組出 j - A[i] 的數量再加一。
            }
        }
    }

    return count(dp + 1, dp + M + 1, true);
}

http://www.cnblogs.com/E-star/archive/2011/12/08/2280973.html
最后是楼教主的o(n*v)的方法。。ORZ啊。。

const int max_s = 107;
int f[100007],w[max_s],b[max_s];
//f[i]来表示当前i价格是否出现过，
int sum[100007];//当价格达到i时，最多使用这一种硬币的次数
int main()
{
    int n,V,i,j;
    while(scanf("%d%d",&n,&V),n+V)
    {
        int ans=0;
        for(i=0;i<n;i++)
        scanf("%d",&w[i]);
        for(i=0;i<n;i++)
        scanf("%d",&b[i]);
        for(i=f[0]=1;i<=V;i++) f[i]=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<=V;j++) sum[j]=0;//关键是用sum来限定了次数
            for(j=w[i];j<=V;j++)//从w[i]到V循环检查看是否能够出现前边没有出现的价格
            {
                if(!f[j]&&f[j-w[i]]&&sum[j-w[i]]<b[i])
                //如果j价格没有出现过，且j-w[i]出现过，并且使用i硬币的次数没有超出给定的数量
                {
                    f[j]=1;//标记为已出现过
                    sum[j]=sum[j-w[i]]+1;//使用次数+1
                    ans++;//满足条件++
                }
            }
        }
        cout<<ans<<endl;
    }
}

https://www.smwenku.com/a/5b7c64302b71770a43dac475