背包九讲之五

动态规划之背包问题

1. 01背包
2. 完全背包
3. 多重背包
4. 二维费用背包
5. 背包剩余容量最小

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;

int C, V, n, w[N], vue[N], val[N], num[N], m[N], dp[N][N]， gd[2][N];

void slove_01bp()///0-1背包
{
    scanf("%d%d", &C, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &w[i], &val[i]);
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; ++i)
        for(int j = C; j >= w[i]; --j)///逆序遍历
            m[j] = max(m[j], m[ j - w[i] ] + val[i]);
    cout << m[C] << '\n';
}

void slove_01gdbp()
{
    scanf("%d%d", &C, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &w[i], &val[i]);
    memset(gd, 0, sizeof(gd));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= C; ++j)
        {
            if(j >= w[i])
                gd[i & 1][j] = max(gd[(i - 1) & 1][j], gd[(i - 1) & 1][j - w[i]] + val[i]);
            else
                gd[i & 1][j] = gd[(i - 1) & 1][j];
        }
    cout << gd[n & 1][C] << '\n';
}

void slove_complate_bp()///完全背包
{
    scanf("%d%d", &C, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &w[i], &val[i]);
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; ++i)
        for(int j = w[i]; j <= C; ++j)///顺序遍历
            m[j] = max(m[j], m[ j - w[i] ] + val[i]);
    cout << m[C] << '\n';
}

void slove_multi_bp()///多重背包(数目有限0/1背包变式)
{
    scanf("%d%d", &C, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d%d", &w[i], &val[i], &num[i]);
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; ++i)
        for(int k = 0; k < num[i]; ++k)
            for(int j = C; j >= w[i]; --j)
                m[j] = max(m[j], m[ j - w[i] ] + val[i]);
    cout << m[C] << '\n';
}

void slove_2D_bp()///二维费用背包(0/1背包变式)
{
    scanf("%d%d%d", &C, &V, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d%d", &w[i], &vue[i], &val[i]);
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; ++i)
        for(int j = C; j >= w[i]; --j)
            for(int k = V; k >= vue[i]; --k)
                dp[j][k] = max(dp[j][k], dp[j-w[i]][k-vue[i]] + val[i]);
    cout << dp[C][V] << '\n';
}

///背包剩余空间最小，即重量最大
///将重量视为价值,即价值最大（0/1背包）
void slove_min_remain_bp()
{
    scanf("%d%d", &C, &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; ++i)
        for(int j = C; j >= w[i]; --j)
         m[j] = max(m[j], m[ j - w[i] ] + w[i]);
    cout << C - m[C] << '\n';
}

int main()
{
    slove_01bp();
    slove_complate_bp();
    slove_multi_bp();
    slove_2D_bp();
    slove_min_remain_bp();
    return 0;
}

背包九讲