01背包问题

朴素算法

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1010;

int v[N], w[N]; // v 代表体积 w 代表权重 y总写的和其他人正好反着。 其他人 w 代表weight v 代表 value 
int f[N][N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);

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

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

    cout << f[n][m] << endl;

    return 0;
}

优化

优化之前先看一下滚动数组。使用滚动数组可以大大减少空间复杂度。

一维数组

老生常谈的斐波那契数列。 1 1 2 3 5 8 13 21 ....
编写一个函数，输入n，返回第n个数(n <= 50)。(实测当 n = 47 爆int)

// 不使用滚动数组
LL fib(int n)
{
    LL fibnacci[55];
    fibnacci[0] = fibnacci[1] = 1;

    if (n == 0 || n == 1) return 1;

    for (int i = 2; i <= n; i++)
        fibnacci[i] = fibnacci[i - 1] + fibnacci[i - 2];

    return fibnacci[n];
}

// 使用滚动数组
// 在求第n个数时，只用到了前面两个值，所以只需开一个长度为三的数组。
LL fib(int n)
{
    LL fibnacci[3];
    fibnacci[0] = fibnacci[1] = 1;

    if (n == 0 || n == 1) return 1;

    while (n - 1)
    {
        n--;
        fibnacci[2] = fibnacci[0] + fibnacci[1];
        fibnacci[0] = fibnacci[1];
        fibnacci[1] = fibnacci[2];
    }

    return fibnacci[2];
}

二维数组

本文最后附上二维数组使用滚动数组与不使用的打印代码点击跳转。

假设递推关系为f[i][j] = f[i - 1][j] + f[i - 1][j - x] (其中 x > 0)

编写一个函数，输入a，b，输出f[a][b]。(i, j <= 50)

// 不使用滚动数组
// 第0行与第0列为递推的出口
int f[50][50], x = 2;

void init()
{
    for (int i = 0; i < 50; i++)
        f[0][i] = 1;
}

int func(int a, int b)
{
    init();
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            if (j >= x) f[i][j] = f[i - 1][j] + f[i - 1][j - x];
    return f[a][b];
}

// 使用滚动数组
// 在求f[i][j]时只用到了前面一行所以可以使用滚动数组
int f[2][50];

void init()
{
    for(int i = 0; i < 50; i++)
        f[0][i] = 1;
}

int func(int a, int b)
{
    init();
    for (int i = 1; i <= a; i++)
    {
        for (int j = 0; j < 50; j++) f[i % 2][j] = 0; // 这个地方很重要 一开始我没有想到 打印时才发现问题
        for (int j = 1; j <= b; j++)
            if (j >= x) f[i % 2][j] = f[1 - i % 2][j] + f[1 - i % 2][j - x]; // 第1行使用第0行，第0行使用第1行
    }
    return f[a % 2][b];
}

优化成一维

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);

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

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

    cout << f[m] << endl;

    return 0;
}

打印代码

由于屏幕大小原因，只打印了20列（查看时建议把窗口拉到最大）

#include<iostream>

using namespace std;

int f[50][50], x = 2;

void init()
{
    for (int i = 0; i < 50; i++)
        f[0][i] = 1;
}

int func(int a, int b)
{
    init();
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            if (j >= x) f[i][j] = f[i - 1][j] + f[i - 1][j - x];
    return f[a][b];
}

int f1[2][50];

void init1()
{
    for (int i = 0; i < 50; i++)
        f1[0][i] = 1;
}

int func1(int a, int b)
{
    init1();
    for (int i = 0; i < 20; i++)
        printf("%10d ", f1[0][i]);
    cout << endl;
    for (int i = 1; i <= a; i++)
    {
        for (int j = 0; j < 50; j++) f1[i % 2][j] = 0;
        for (int j = 1; j <= b; j++)
            if (j >= x) f1[i % 2][j] = f1[1 - i % 2][j] + f1[1 - i % 2][j - x];
        for(int j = 0; j < 20; j++)
            printf("%10d ", f1[i % 2][j]);
        cout << endl;
    }
    return f1[a % 2][b];
}

int main()
{
    func(49, 49);

    for (int i = 0; i < 50; i++)
    {
        for (int j = 0; j < 20; j++)
            printf("%10d ", f[i][j]);
        cout << endl;
    }

    cout << "===============================================分割线================================================" << endl;

    func1(49, 49);

    system("pause");
    return 0;
}

参考文献

y总讲解。
https://blog.csdn.net/weixin_40295575/article/details/80181756