题目：AcWing 2. 01背包问题

DP写法：

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + w);
    }
    printf("%d\n", f[m]);
    return 0;
}

暴力写法：

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
        scanf("%d%d", &v[i], &w[i]);

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
    {
        int sumv = 0, sumw = 0;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
            {
                sumv += v[j];
                sumw += w[j];
            }
        if (sumv <= m) res = max(res, sumw);
    }

    printf("%d\n", res);
    return 0;
}

数据生成器代码

#include <iostream>
#include <fstream>

using namespace std;

void generate_data()
{
    ofstream fout("input.txt");
    int n = 10, m = rand() % 100 + 50;
    fout << n << ' ' << m << endl;

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

int main()
{
    for (int i = 0; i < 100; i ++ )
    {
        printf("iteration: %d\n", i);
        generate_data();
        system("Dp.exe < input.txt > dp_output.txt");
        system("bruteforce.exe < input.txt > bf_output.txt");
        if (system("fc dp_output.txt bf_output.txt"))
        {
            puts("错啦!");
            break;
        }
    }

    return 0;
}