动态规划(01背包问题)

类型

01背包：每件物品最多只用一次
完全背包：每件物品有无限个
多重背包：每个物品的个数不同

01背包：

方法

题目1：https://www.acwing.com/problem/content/description/2/

有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

思路：

枚举第 $i$ 个物品，枚举 $j$ 背包的体积
不选择第 $i$ 个物品或容量大于 $j$ ，则当前最大价值为 $dp[i-1][j]$
选择第 $i$ 个物品，那么找到去除当前物品 $i$ 所占体积，也就是 $j-w[i]$ ，再找二维数组所存的最大价值，最后加上 $v[i]$ ，得到 $dp[i-1][j-w[i]] + v[i]$

二维：

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

using namespace std;

const int N = 1010;
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 = m; j >= 0; 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;
            
}

一维：

只需将f[i][j]优化到一维f[j]，

为什么能这样做？由二维的递推方程 $f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i])$ 可知，每一层都是用上一层来更新的，

举个例子： $f[4][8] = max(f[3][8], f[3][7]+4)$ ，也就是说我们只需要 $i-1$ 层的数据。
所以我们就可以用 $f[j]$ 来记录 $f[i][j]$ 的数据，在更新的过程中不断覆盖。
但是如果直接正序覆盖的话，将会出错，因为我们使用的是 $i -1$ 层的数据，替换到 $f[j]$ 时，不能保证 $f[7]$ 存储的是 $f[3][7]$ 的值，也就是不是用上一轮的数据来更新这一轮的数据，因此需要倒序遍历。
如果是倒序遍历，则枚举的 $j$ 体积都要比原先的 $j$ 小，所以当某个位置更新数据时，就不会调用其位置后面的数据。

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

using namespace std;

const int N = 1010;
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] << endl;

    return 0;
            
}

完全背包：

题目：https://www.acwing.com/activity/content/problem/content/998/

capture_20221016130901518

朴素做法：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
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++)
            for(int k = 0; k*v[i]<=j; k++)
                //f[i-1][j]就是k等于0的时候的表达式
                f[i][j] = max(f[i][j],f[i-1][j - v[i]*k] + w[i] * k);
   	cout << f[n][m] << endl;
    
    return 0;
}

优化：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

极简版：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
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[n] << endl;
    
    return 0;
}

多重背包：

题目：https://www.acwing.com/problem/content/4/

capture_20221016130622624(2)

/*
f[i][j]= max(f[i-1][j -v[i] *k]+w[i]*k); k = 0, 1, 2;
*/
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int v[N], w[N], s[N];
int f[N][N];
int n, m;
int main()
{
    cin >> n>> m;
    for (int i = 1; i <= n; i ++) cin >>v[i]>> w[i] >>s[i];
    
    for (int i = 1; i <= n; i ++) //枚举背包
        for(int j = 1; j <= m; j ++) // 枚举体积
            for (int k = 0; k <= s[i] && k *v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    cout << f[n][m] << endl;
    
    return 0;
}

优化

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

const int N = 25000, M = 2010;

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

int main()
{
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1 ; i <= n; i ++)
    {
        int a, b, s;
        cin >> a>> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    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;
}