题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//背包问题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =15;
const int M = 1e4+5;
int f[N][M];
int a[N];
int n,m;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&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]<<endl;
    return 0;
}
//优化后的背包问题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =15;
const int M = 1e4+5;
int f[M];
int a[N];
int n,m;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    f[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            f[j]+=f[j-a[i]];
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//也可以直接暴搜
#include <iostream>
using namespace std;

const int N = 1010;

int n, m;
int a[N];  // 用于存储输入的n个不同正整数
int cnt;

// DFS函数，cur表示当前考虑的数字下标，sum表示当前已选数字的和
void Dfs(int cur, int sum) {
    if (sum == m) {
        cnt++;
        return;
    }

    if (cur == n || sum > m) return;  // 如果已经遍历完所有数字或者当前和超过了m，就回溯

    // 不选当前数字，继续考虑下一个数字
    Dfs(cur + 1, sum);
    // 选择当前数字，然后继续考虑下一个数字
    Dfs(cur + 1, sum + a[cur]);

}

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

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

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