动态规划笔记(二):背包问题（未整理完）

背包问题

0/1背包问题（HDU-2602）

状态转移方程：\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])\)

• 递推

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

const int N = 1010;
int w[N], v[N], dp[N][N];

void solve()
{
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    for (int i = 1; i <= n; i ++ ) cin >> v[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= V; j ++ )	// 这题j必须从0开始不然WA，可能是因为存在v[i] = 0
        {
            if (j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            else dp[i][j] = dp[i - 1][j];
        }
    cout << dp[n][V] << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t -- )
    {
        solve();
    }

    return 0;
}

时间复杂度为\(O(nV)\)

• 记忆化

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

const int N = 1010;
int w[N], v[N], dp[N][N];

int solve(int i, int j)
{
    if (dp[i][j]) return dp[i][j];
    if (i == 0) return 0;
    if (j >= v[i]) return dp[i][j] = max(solve(i - 1, j), solve(i - 1, j - v[i]) + w[i]);
    return dp[i][j] = solve(i - 1, j);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t -- )
    {
        memset(dp, 0, sizeof dp);
        int n, V;
        cin >> n >> V;
        for (int i = 1; i <= n; i ++ ) cin >> w[i];
        for (int i = 1; i <= n; i ++ ) cin >> v[i];
        cout << solve(n, V) << '\n';
    }

    return 0;
}

时间复杂度为\(O(nV)\)

• 滚动数组优化

由状态转移方程可得，\(dp[i][]\)只与\(dp[i - 1][]\)有关，因此可用滚动数组优化空间

1. 交替滚动

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

const int N = 1010;
int w[N], v[N], dp[2][N];

void solve()
{
    memset(dp, 0, sizeof dp);
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    for (int i = 1; i <= n; i ++ ) cin >> v[i];
    int now = 0, prev = 1;
    for (int i = 1; i <= n; i ++ )
    {
        swap(now, prev);
        for (int j = 0; j <= V; j ++ )
            if (j >= v[i]) dp[now][j] = max(dp[prev][j], dp[prev][j - v[i]] + w[i]);
            else dp[now][j] = dp[prev][j];
    }
    cout << dp[now][V] << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t -- )
    {
        solve();
    }

    return 0;
}

时间复杂度不变，但空间复杂度由原先的\(O(nV)\)变为\(O(V)\)

2. 自我滚动

   注意：\(j\)必须从大到小遍历

   #include <iostream>
   #include <algorithm>
   #include <cstring>
   using namespace std;
   
   const int N = 1010;
   int w[N], v[N], dp[N];
   
   void solve()
   {
       memset(dp, 0, sizeof dp);
       int n, V;
       cin >> n >> V;
       for (int i = 1; i <= n; i ++ ) cin >> w[i];
       for (int i = 1; i <= n; i ++ ) cin >> v[i];
       // for (int i = 1; i <= n; i ++ )
       //     for (int j = V; j >= 0; j -- )
       //         if (j >= v[i]) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
       // 下方与上方被注释的代码等价
       for (int i = 1; i <= n; i ++ )
           for (int j = V; j >= v[i]; j -- )
               dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
       cout << dp[V] << '\n';
   }
   
   int main()
   {
       ios::sync_with_stdio(false);
       cin.tie(0);
   
       int t;
       cin >> t;
       while (t -- )
       {
           solve();
       }
   
       return 0;
   }
   

同样时间复杂度不变，空间复杂度由原先的\(O(nV)\)变为\(O(V)\)

完全背包问题（Acwing）

状态转移方程:\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i], ..., dp[i - 1][j - k * v[i]] + k * w[i])\)

• 朴素做法(TLE)

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

const int N = 1010;
int w[N], v[N], dp[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= V; j ++ )
            for (int k = 0; k * v[i] <= j;  k ++ )
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
    cout << dp[n][V] << '\n';

    return 0;
}

这个时间复杂度不会算，但最坏情况下时间复杂度可以估成\(O(nV^2)\)

• 时间优化

由状态转移方程\(dp[i][j - v[i]] = max(dp[i - 1][j - 2 * v[i]] + w[i], ...,dp[i][j - k * v[i]] + (k - 1) * w[i])\)可得：\(dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])\)

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

const int N = 1010;
int w[N], v[N], dp[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= V; j ++ )  // j必须从小到大遍历
            if (j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
            else dp[i][j] = dp[i - 1][j];
    cout << dp[n][V] << '\n';

    return 0;
}

时间复杂度为\(O(nV)\)

• 交替滚动

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

const int N = 1010;
int w[N], v[N], dp[2][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    int now = 0, prev = 1;
    for (int i = 1; i <= n; i ++ )
    {
        swap(now, prev);
        for (int j = 1; j <= V; j ++ )
            if (j >= v[i]) dp[now][j] = max(dp[prev][j], dp[now][j - v[i]] + w[i]);
            else dp[now][j] = dp[prev][j];
    }
    cout << dp[now][V] << '\n';

    return 0;
}

时间复杂度与时间优化后一样，空间复杂度由时间优化后的\(O(nV)\)变为\(O(V)\)