数字组合

题目 数字组合

image-bd740573

思路分析

01背包的变形 这次我们集合的属性不再是max了

而是count

image-2e50140e

代码实现

dfs(tle)

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=10010;
int v[N];
int f[N][N];
int n,m;
int cnt=0;
void dfs(int u,int sum){
	if(u>n){
		if(sum==m)	cnt++;
		return;
	}
	dfs(u+1,sum+v[u]);
	dfs(u+1,sum);
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)	cin>>v[i];

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

朴素做法 27 ms

#include<bits/stdc++.h>
using namespace std;

const int N=110,M=10010;
int v[N];
int f[N][M];
int n,m;

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

    //从i个物品中选 且总价值等于0的方案数都是一个（什么都不选也是一种选法）
    for(int i=0;i<N;i++)
        f[i][0]=1;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //空间不够时 不能选第i个物品 此时的方案数为：
            f[i][j]=f[i-1][j];
            //空间够时 就还得加上选第i个物品（右边集合）的方案数
            if(j>=v[i])
                f[i][j]+=f[i-1][j-v[i]];
        }
    }

    cout<<f[n][m];

    return 0;
}

滚动数组优化 16 ms

#include<bits/stdc++.h>
using namespace std;

const int N=110,M=10010;
int v[N];
int f[M];
int n,m;

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

    f[0]=1;

    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]+=f[j-v[i]];

    cout<<f[m];

    return 0;
}

v[i]可不存 循环合并 14 ms

#include<bits/stdc++.h>
using namespace std;

const int M=10010;
int f[M];
int n,m;

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

    f[0]=1;

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

    return 0;
}

同类题型

视频讲解

⬅️ 开心的金明 🏠 00-刷题理模型 ➡️ 糖果