题目描述

数字组合问题，可以 优化，优化方式与01背包相同

求count，及两部分的数量，不再用max或min，而是用相加的方式

#include <iostream>

using namespace std;
const int N=10010;

int a[N],f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int cnt=0;
    //一个都不选，可以构成一种方案
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=1;
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
        }
    }
    cout<<f[n][m];

    return 0;
}

二刷 另外一种思路，多加了个判断，其实发现是N开小了，因为第二维要和m一般大，要开到10100就可以直接不用加判断了

#include <iostream>

using namespace std;

const int N=10100;

int f[N][N],a[N];

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

    f[0][0]=1;

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

    return 0;
}

2023/11/27

01背包问题，”恰好”求方案数
要点：
1. fij: 从前i个数中选，总和”恰好”为j的方案数
2. f[0][0]初始化为1

#include <iostream>
#include <cstring>

using namespace std;

const int N=10010;
int n,m;
// fij: 从前i个数中选，总和"恰好为"j的方案数
int f[N][N];
int a[N];

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

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


    f[0][0] = 1;

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

    cout<<f[n][m];

    return 0;
}