背包问题

1. 0-1背包


/*

f[i][j] : 只考虑前i个物品，在体积为j的情况下的最大价值
res = max(f[n][0...V])

状态转移:

f[i][j] := 

s0. 不装第i个物品  = f[i-1][j]
s1. 装下第i个物品  = f[i-1][j-v[i]] + w[i]

max(s0,s1)

f[0][j] = 0;
f[i][0] = 0;

时间和空间复杂度O(N^2) ~ 1000*1000
*/

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1001;
int f[N][N];
int n, m;
int v[N], w[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=1; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            if(j >= v[i])
                f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    cout<< f[n][m] <<endl;
    return 0;
}

---优化空间复杂度到O(N)

/*
1, 考虑一维数组代替二维数组，即删除f[i][j]的第一个维度
2，容量递减循环，保证由i-1的状态推出i的状态，且每个物体只使用一次
3，j<v[i]的状态转移不需要了
*/
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1001;
int f[N];
int n, m;
int v[N], w[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] <<endl;
    return 0;
}

---以上求的是不大于背包容量的情况下的最大价值?，如果是恰好装满的情况，只需要修改初始化代码

/*
初始化 f[0] = 0;
  其余 f[1...V] = 0x80000000;
*/

2. 完全背包

/*
与0-1背包的差异:
完全背包递增枚举容量
*/
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;
int n, c; //数量，容积
int f[N];

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

3. 多重背包

/*
每种物品有一定数量

for(int i=0; i<n; i++)
{
    for(int j=c; j>=v[i]; j--)
    {
        f[j] = max(f[j], f[j - v[i] + w[i], f[j-2*v[i]] + 2*w[i],...); //0,1,2...s种选法
    }
}
不同初始化方法对应的最大值
1, f[i] = 0;
f[c]
2, f[0] = 0, 其余f[i] = -INF
max(f[0....c])

~O(N^3)
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 101;
int f[N];
int n, c;

int main()
{
    cin >> n >> c;
    int v, w, s;  //体积、价值、数量
    for(int i = 0; i < n; i++)
    {
        cin >> v >> w >> s;
        for(int j = c; j >= v; j--)
        {
            for(int k = 0; k <= s && k * v <= j; k++)
            {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[c] << endl;
    
    
}

数据量较大的情况下，需要优化时间复杂度，可以采用二进制优化方法：

/*数据量较大的情况下，需要优化时间复杂度
O(V∑n[i]) --> O(V∑log(n[i]))
将s个第i种物品拆分为floor(log(s))个:
 7 = 1 + 2 + 4;
 10 = 1 + 2 + 4 + 3; 10 - 1 - 2 - 4
*/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int V = 2001;
int f[V];
int n, c; //实际输入物品个数，背包容积

struct Goods
{
    int v, w;
};

int main()
{
    vector<Goods> goods; 
    cin >> n >> c;
    for(int i = 0; i < n; i++)
    {
        int v, w, s; //体积，价值，数量
        cin >> v >> w >> s;
        for(int k = 1; k <= s; k *= 2)
        {
            s -= k;
            goods.push_back({v * k , w * k});
        }
        if(s > 0)
            goods.push_back({v * s, w * s});
    }
    for(auto g : goods)
        for(int j = c; j >= g.v; j--)
        {
            f[j] = max(f[j], f[j - g.v] + g.w);
        }
        
    cout << f[c] << endl;
}

数据量很大的情况下，需要考虑单调队列优化

// O(NV)
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 20010;

int f[2][N], q[N];
int n, c;
int main()
{
    cin >> n >> c;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        for(int op = 0; op < c; op++)
            f[0][op] = f[1][op]; // f[1][]<->f[i][], f[0][]<->f[i-1][] 
        for(int r = 0; r < v; r++)
        {
            int head = 0, tail = -1;
            for(int k = r; k <= c; k += v)
            {
                if(head <= tail && q[head] < k - s*v)
                    head++;
                if(head <= tail)
                    f[1][k] = max(f[1][k], f[0][q[head]] + (k - q[head])/v * w);
                while(head <= tail && f[0][q[head]] - (q[head] - r)/v *w <= f[0][k] - (k - r)/v * w)
                    tail--;
                q[++tail] = k;
            }
        }
    }
    cout<<f[1][c];
    return 0;
}

4. 混合背包

求解这类问题只需要把混合背包分解01背包和完全背包。其中的多重背包可以考虑采用二进制优化分解为01背包。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;
int f[N];
int n, m;

struct Thing
{
    int type;
    int v, w;
};

vector<Thing> things;

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

5. 二维费用的背包

类似一维背包，只是状态转移方程多了一维

/*
f[i][j] 表示容量为i,重量为j的情况下的最大价值
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 101;
int f[N][N];
int n, V, M;

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

6. 分组背包

每组中的物品只能选择一件，对于具有s件物品的某一组，具有s+1种选择：一件都不选，选第0件，...，选第s-1件。

/*
for(int i  = 0; i < n; i++)
{
    for(int j = m; j >= v; j--)
    {
        f[j] = max(f[j], f[j-v[0]] + w[0], f[j-v[1]]+w[1],...,f[j-v[s-1]]+w[s-1]);
    }
}
输出f[m]
*/

#include <iostream>
#include <algorithm>
using namespace std;

const int N =101;
int f[N], v[N], w[N];

int n, V;

int main()
{
    cin >> n >> V;
    for(int i = 0; i < n; i++)
    {
        int s;
        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;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。