例题为 2. 01背包问题。

参考标程：

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("DP.txt", "w", stdout);

    cin >> n >> m;

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

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

参考暴力写法

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

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int ans;

void dfs(int u, int sum, int value)
{
    if (u == n) ans = max(ans, value);
    else
    {
        dfs(u + 1, sum, value);

        if (sum + v[u] <= m)
            dfs(u + 1, sum + v[u], value + w[u]);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("DFS.txt", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; i ++ ) cin >> v[i] >> w[i];

    dfs(0, 0, 0);

    cout << ans << endl;
    return 0;
}

参考数据生成器

#include <iostream>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <ctime>

using namespace std;

void create_dataset()
{
    ofstream fout("input.txt");

    int n = rand() % 20 + 1, m = rand() % 1001;

    fout << n << ' ' << m << endl;

    for (int i = 0; i < n; i ++ )
    {
        int v = rand() % 1001, w = rand() % 1001;
        fout << v << ' ' << w << endl;
    }

    fout.close();
}

bool work()
{
    create_dataset();

    system("DP.exe");
    system("DFS.exe");

    return !system("fc DP.txt DFS.txt");
}

int main()
{
    srand(time(0));

    for (int i = 0; i < 100000; i ++ )
    {
        if (!work()) break;
    }

    return 0;
}