01背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int f[N];

int main()
{
    int n, m; 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>

using namespace std;

const int N = 1010;

int f[N];

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

多重背包问题

//自己和自己转移  f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
#include <iostream>
#include <cstring>

using namespace std;
const int N = 110;

int f[N][N];

int main()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int v, w, s; cin >> v >> w >> s;
        for(int j = 0; j <= m; j ++)
        {
            for(int k = 0; k <= s && k * v <= j; k ++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

多重背包问题 01

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2010;

int f[N];

int main()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int v, w, s; cin >> v >> w >> s;
        for(int k = 1; k <= s; k = k << 1)
        {
            for(int j = m; j >= k * v; j --)
            {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
            s -= k;
        }
        if(s)
        {
            for(int j = m; j >= s * v; j --)
            {
                f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

分组背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

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

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

AcWing 423. 采药

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int f[N];

int main()
{
    int m, n; cin >> m >> n;
    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;
}

AcWing 1024. 装箱问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20000 + 10;

int f[N];

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

AcWing 1022. 宠物小精灵之收服【二维费用01背包问题】

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 510;

int f[N][M];

int main()
{
    int V1, V2, n; cin >> V1 >> V2 >> n;
    for(int i = 1; i <= n; i ++)
    {
        int v1, v2; cin >> v1 >> v2;
        for(int j = V1; j >= v1; j --)
        {
            for(int k = V2 - 1; k >= v2; k --)
            {
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
            }
        }
    }
    cout << f[V1][V2 - 1] << ' ';
    int res = V2;
    for(int i = 0; i <= V2; i ++)
    {
        if(f[V1][i] == f[V1][V2 - 1]) res = min(res, i);
    }
    cout << V2 - res;
}

AcWing 278. 数字组合

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10000 + 10;

int f[N], v[N];

int main()
{
    int n, m; 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] << endl;
    return 0;
}

AcWing 1023. 买书

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int w[] = {0, 10, 20, 50, 100};
int f[N];
int main()
{
    int n; cin >> n;
    f[0] = 1;
    for(int i = 1; i <= 4; i ++)
    {
        for(int j = w[i]; j <= n; j ++)
        {
            f[j] += f[j - w[i]];
        }
    }
    cout << f[n] << endl;
    return 0;
}

AcWing 1021. 货币系统

#include <iostream>
#include <cstring>

#define int long long
using namespace std;

const int N = 3010;

int f[N];

signed main()
{
    int n, m; cin >> n >> m;
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        int v; cin >> v;
        for(int j = v; j <= m; j ++)
        {
            f[j] += f[j - v];
        }
    }
    cout << f[m] << endl;
    return 0;
}