多重背包解析——凑面值

多重背包
大家应该都知道过程了吧，这里不多介绍了 直接贴代码
题目
给定几种不同面额的硬币若干枚，需要求的用这些硬币可以组成多少种范围在1~m的不同面额的组合。
Input
输入包含多组数据，每组数据第一行有两个数字n(1 ≤ n ≤ 100)，m(m ≤ 100000)。第二行包含2n个数字, A1,A2,A3…An,C1,C2,C3…Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000)——Ai表示第i种硬币的面值，Ci表示第i种硬币的数量，输入以0 0结束。
Output
对于每组数据输出可能的组合数。
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4

这是典型的多重背包裸题

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
int a[MAXN], b[MAXN], dp[MAXN], n, m;
int main()
{
    while (~scanf("%d%d", &n, &m) && n != 0 && m != 0)
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &b[i]);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            int k = 1;
            while (k <= b[i])
            {
                for (int j = m; j >= k * a[i]; j--)
                {
                    dp[j] |= dp[j - k * a[i]];
                }
                b[i] -= k;
                k *= 2;
            }
            if (b[i] == 0)
                continue;
            for (int j = m; j >= b[i] * a[i]; j--)
            {
                dp[j] |= dp[j - b[i] * a[i]];
            }
        }
        LL ans = 0;
        for (int i = 1; i <= m; i++)
        {
            ans += dp[i];
        }
        cout << ans << endl;
    }
    return 0;
}

这道题因为数据有点大我用了位优化

不懂可以问我 谢谢

加QQ 1446035688

最后

以上就是美好香水为你收集整理的多重背包解析——凑面值的全部内容，希望文章能够帮你解决多重背包解析——凑面值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。