背包问题合集

##背包问题模板代码整理

01背包

#include<iostream>
using namespace std;
const int N = 1005;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
 cin >> n >> m;
 for (int i = 1; i <= n; i++)cin >> 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];
 return 0;
}

//优化代码
#include<iostream>
using namespace std;
const int N = 1005;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    cin >> 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];
    return 0;
}

完全背包问题

//朴素版本
#include<iostream>
using namespace std;
const int N = 1005;
int n, m;
int v[N], w[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> 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][j - v[i]] + w[i]);
            //for (int k = 0; k * v[i] <= j; k++)
            //{
            //    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                  //推导式
            //}
        }
    }
    cout << f[n][m];
    return 0;
}
//优化代码
#include<iostream>
using namespace std;
const int N = 1005;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
    {
        for (int j = v[i]; j <= m; j++)
        {
           f[j] = max(f[j] , f[j - v[i]] + w[i]);
        }
    }
    cout << f[m];
    return 0;
}

多重背包问题

//一.朴素版（拆成01背包O(n^3))
#include <iostream>
using namespace std;
int a[10005], b[10005], n, m, dp[10005] = {};
int w, v, s;
int main()
{
    cin >> n >> m;
    while (n--)
    {
        cin >> v >> w >> s;
        //死拆，把多重背包拆成01背包
        for (int j = m; j >= 0; j--)
            for (int k = 0; k * v <= j && k <= s; k++)
                dp[j] = max(dp[j - k * v] + k * w, dp[j]);//直接套01背包的板子
    }
    cout << dp[m] << endl;
    return 0;
}
//二进制优化(O(n^2*log2s))
#include <iostream>
#include <vector>
using namespace std;
const int N = 2005;
int  n, m, f[N];
int w, v, s;
struct a { 
    int v,w;
};
vector<a> ans;
int main()
{
    cin >> n >> m;
    while (n--)
    {
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k*=2)
        {
            s -= k;
            ans.push_back({ v * k,w * k });
        }
        if (s > 0)ans.push_back({ v * s,w * s });//余数（够不到2次幂的数）
        for (auto x : ans)//01背包
        {
            for (int j = m; j >= x.v; j--)
            {
                f[j] = max(f[j], f[j - x.v] + x.w);
            }
        }
    }
    cout << f[m];
    return 0;
}

//单调队列优化（O(n*m)）m指v的最大值

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2010;
int n, m;
int f[N], g[N], q[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int c, w, s;
        cin >> c >> w >> s;
        memcpy(g, f, sizeof(f));
        for (int j = 0; j < c; j++)
        {
            int hh = 0, tt = -1;//初始化空双端队列
            for (int k = j; k <= m; k += c)
            {
                f[k] = g[k];
                if (hh <= tt && k - s * c > q[hh])hh++;
                if (hh <= tt)f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / c * w);
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / c * w <= g[k] - (k - j) / c * w)tt--;
                q[++tt] = k;
            }
        }
    }
    cout << f[m];
    return 0;
}

混合背包问题

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

using namespace std;

int N, V;
int f[1010];

int main()
{
    cin >> N >> V;

    for (int i = 1; i <= N; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == 0)//完全背包
        {
            for (int j = v; j <= V; j++) f[j] = max(f[j], f[j - v] + w);
        }
        else {
            if (s == -1) s = 1;//若为01则初始化为1，若为多重背包则初始化为二进制表示以优化
            for (int k = 1; k <= s; k *= 2) {
                for (int j = V; j >= k * v; j--)
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            if (s)//统一公式处理01和多重背包
            {
                for (int j = V; j >= s * v; j--) {
                    f[j] = max(f[j], f[j - s * v] + s * w);
                }
            }
        }
    }
    cout << f[V] << endl;
    return 0;
}

二维费用背包

#include<iostream>
using namespace std;
const int N = 1005;
int n, m, w;
int f[N][N];
int main()
{
    cin >> n >> m >> w;
    for (int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        for (int j = m; j >= a; j--)
        {
            for (int k = w; k >= b; k--)
            {
                f[j][k] = max(f[j][k], f[j - a][k - b] + c);
            }
        }
    }
    cout << f[m][w];
    return 0;
}

分组背包

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int f[N];  //只从前i组物品中选，当前体积小于等于j的最大值
int V[N] , W[N] , s;   //v为体积，w为价值，s代表第i组物品的个数
int n , v;

int main(){
    cin >> n >> v;//读入
    for(int i = 0 ; i < n ; i++)
    {
        cin >> s;
        for(int j = 0 ; j < s ; j++)cin>>V[j]>>W[j];
        for(int j = v ; j >= 0 ; j--)
        {
            for(int k = 0 ; k < s ; k++)
            {//选择第几个物品好
                if(j >= V[k]) f[j] = max( f[j] , f[j-V[k]] + W[k] );  
            }
        }
    }
    cout << f[v] <<endl;
}