AcWing 278. 数字组合

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 278. 数字组合原题链接简单

作者：

yxc , 2019-10-12 04:17:12 , 所有人可见 , 阅读 13722

70

13

算法

(DP,01背包问题) $O(nm)$

可以转化为01背包问题求方案数：

将总和 $M$ 看作背包容量；
将每个数 $A_i$ 看作体积为 $A_i$ 的物品；

时间复杂度

背包问题的时间复杂度是 $O(nm)$ 。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    f[0] = 1;
    for (int i = 0; i < n; i ++ )
    {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- ) f[j] += f[j - v];
    }

    cout << f[m] << endl;

    return 0;
}

19 评论

流川枫爱吃橙子吗 2023-04-04 20:05

这里贴一个未优化的代码帮助理解

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010;

int n, m;
int f[110][N];

int main()
{
    cin >> n >> m;

    //从前i个物品中选，且价值为0的方案数均为1
    //什么都不选就是一种选法
    for(int i = 0; i < 110; i ++)
        f[i][0] = 1;

    for(int i = 1; i <= n; i ++)
    {
        int v;
        cin >> v;

        for(int j = 0; j <= m; j ++)
        {
            //不选当前物品
            f[i][j] = f[i - 1][j];
            //选当前物品
            //选法为从前i - 1个数中选且价值为j - v的所有选法
            //即f[i - 1][j - v]
            if(j >= v)
                f[i][j] += f[i - 1][j - v];
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

strui 2024-04-03 22:56

想了一下可以暴搜，就卡了1个数据

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int a[N];
int cnt = 0;
int n, m;

void dfs(int u, int sum)//u是选第几个数，sum是当前的和
{
    if(u > n)
        return;
    if(sum > m)
        return;
    if(sum == m)
    {
        cnt ++;
        return;
    }
    dfs(u + 1, sum);//不加当前这个数
    dfs(u + 1, sum + a[u]);//加当前这个数
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> a[i];

    dfs(0, 0);
    cout << cnt << endl;
    return 0;
}

gblong10 2021-03-22 14:49

之前听y总讲01背包恰好装满问题，要在初始化将数组初始化为负无穷，然后f[0] = 0，这样可以保证最后的答案是由f[0]转移过来的，那这个题也是要求恰好装满（即总和恰好达到m），这个如何保证呢

告别北极的忙碌小熊 2021-05-02 19:04

同问

林小胖 2021-07-24 16:45

您好请问有答案了吗

kimmmm 2021-08-25 21:23

这里恰好达到m是通过初始化f[0]=1,其余的f[i]=0得到的，可以保证最后的结果f[m]是由f[0]转移过来的，如果是从f[i],i不等于0的状态转移，那么最后的结果f[m]始终是0；如果想要总和是小于等于m，全部的f[i]初始化为1即可。

平凡 2021-11-05 15:15

请问有答案了吗

jiebu 2022-03-02 10:19 回复了 kimmmm 的评论

太清晰了

chanxe 2022-12-10 13:45

这里背包的意义是方案数，初始化时其他除了0外其他容量的背包都没法装满，所以方案数为0.f[0] = 1, f[i] = 0

wzc 2021-07-21 11:16

orz

MuQYY 2024-07-14 16:21

显式的滚动数组，可能容易理解点

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int f[2][N]; // f[i][j]表示从前i个数中选择, 和为j的方案数
int a[105];
int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < 2; i++) f[i][0] = 1; // 什么也不选这是一种选法

    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i & 1][j] = f[i - 1 & 1][j];
            if(j >= a[i])
            {
                f[i & 1][j] += f[i - 1 & 1][j - a[i]];
            }
        }
    cout << f[n & 1][m] << endl;
    return 0;
}

lmh_h 2024-01-27 13:24

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int a[N], dp[10010];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ )
    {

        for (int j = m; j >= a[i]; j -- )
        {
            dp[j] += dp[j - a[i]];
        }
        dp[a[i]] ++;
    }

    cout << dp[m] << endl;
    return 0;
}