01 背包-采药


  • 采药

    1、采药:输入 T 和 M 分别表示拥有的总时间药材种类(T 不超过 1000,M 不超过 100),对于每种药材,输入 t 和 v(都不超过 100),表示采摘该药材需要的时间药材的价值,每种药材只可采摘一次。可能输入多组数据,直到 T 和 M 都为 0 结束。对于每组数据,输出其规定时间内能采摘的药材价值之和的最大值
    2、对于每种药材都可以用 0 或 1 标记状态(是否被选择),是一个01 背包问题。运用动态规划的思想,先确定状态:令dp[i][j]表示到第 i 个物品为止用了 j 的时间所获得的最大价值
    3、再确定转移,对于当前的dp[i][j],有两种情况:如果没选择当前第 i 个物品,则dp[i][j] = dp[i-1][j](没有花费时间,没有增加价值,和上一个——到第 i-1 个物品的状态相同);如果选择了当前第 i 个物品,则dp[i][j] = dp[i-1][j-t[i]] + v[i](当前状态等同于dp[i-1][j-t[i]]上一个物品的价值 + 当前物品价值,其中因为当前dp[i][j]花费的总时间为 j,所以上一个物品的时间应为j-t[i])
    4、最后确定初始化和边界初始化dp[0][i] = 0(到第 0 个物品无论花费多少时间,价值为 0);边界为 i <= M, j <= T

  • 代码实现

    #include <bits/stdc++.h>
    using namespace std;
    
    int T, M;
    int dp[110][1010]; // dp[i][j] 表示到第 i 个物品花费 j 的时间的最大价值
    int t[110], v[110];
    
    void solve()
    {
        // 初始化
        for (int i = 0; i <= T; i++)
            dp[0][i] = 0;
    
        // 输入
        for (int i = 1; i <= M; i++)
            cin >> t[i] >> v[i];
    
        // 注意转移方程中,其中一种为 dp[i][j] = dp[i-1][j-t[i]] + v[i],令 i_ = i-1,j_ = j-t[i]
        // 则隐含 i_ < i, j_ < j,所以遍历方向一定要从小到大
        // 状态转移,dp[i][j] = dp[i-1][j] 或 dp[i-1][j-t[i]] + v[i],取大值
        for (int i = 1; i <= M; i++)
        {
            for (int j = 0; j <= T; j++)
            {
                // 注意判断时间的合法性,不要越界
                if (j - t[i] >= 0)
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + v[i]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
    
        // 输出,到第 M 个物品花费 T 时间的最大价值
        cout << dp[M][T] << '\n';
    }
    
    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        while (cin >> T >> M)
        {
            if (T == 0 && M == 0)
                break;
            solve();
        }
        return 0;
    }
  • 滚动数组优化

    1、回顾之前的思路中,dp[i][j]所需的值只有dp[i-1][j]dp[i-1][j-t[i]],而当更新完当前dp[i][j]后,前一行dp[i-1]不需要了。因此,实际需要的行数只需要两行,一行表示当前行,一行表示前一行
    2、由于数组的拷贝需要开销,所以可以换一种方法实现。只开两行的数组dp[0][]dp[1][]当前更新第 0 行时就由第 1 行的状态转移过来,反之亦然。这样交替更新,就实现了滚动数组,节省空间
    3、具体地,可以通过奇偶性位运算实现。用cur = i & 1标记哪一行表示当前行,则cur ^ 1即为另一行(上一行)。最后输出时即输出最后一行cur的那一行,即dp[M & 1][T]

    #include <bits/stdc++.h>
    using namespace std;
    
    int T, M;
    int dp[2][1010]; // dp[i][j] 表示到第 i 个物品花费 j 的时间的最大价值
    int t[110], v[110];
    
    void solve()
    {
        // 初始化
        for (int i = 0; i <= T; i++)
            dp[0][i] = 0;
    
        // 输入
        for (int i = 1; i <= M; i++)
            cin >> t[i] >> v[i];
    
        // 注意转移方程中,其中一种为 dp[i][j] = dp[i-1][j-t[i]] + v[i],令 i_ = i-1,j_ = j-t[i]
        // 则隐含 i_ < i, j_ < j,所以遍历方向一定要从小到大
        // 状态转移,dp[i][j] = dp[i-1][j] 或 dp[i-1][j-t[i]] + v[i],取大值
        for (int i = 1; i <= M; i++)
        {
            // 滚动数组优化,cur 表示当前行,cur ^ 1 表示上一行(另一行)
            int cur = i & 1;
    
            for (int j = 0; j <= T; j++)
            {
                // 注意判断时间的合法性,不要越界
                if (j - t[i] >= 0)
                    dp[cur][j] = max(dp[cur ^ 1][j], dp[cur ^ 1][j - t[i]] + v[i]);
                else
                    dp[cur][j] = dp[cur ^ 1][j];
            }
        }
    
        // 输出,到第 M 个物品(最后一行的 cur = M & 1)花费 T 时间的最大价值
        cout << dp[M & 1][T] << '\n';
    }
    
    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        while (cin >> T >> M)
        {
            if (T == 0 && M == 0)
                break;
            solve();
        }
        return 0;
    }
  • 一维优化

    1、在滚动数组dp[cur][j] = max(dp[cur ^ 1][j], dp[cur ^ 1][j - t[i]] + v[i]);,其本质可看作先将上一行复制到当前行,再进行转移比较,因此可以再将其压缩为一维(省去了复制的步骤),dp[j]表示到目前为止花费了 j 时间最大价值
    2、此时转移方程变为dp[j] = max(dp[j], dp[j - t[i]] + v[i]),但转移时应使用上一行时的数据,如果自左向右遍历,左侧的数据已被更新(即dp[j - t[i]]已经变为当前行数据)。因此要自右向左遍历,范围从最大时间开始,始终满足j - t[i] >= 0

    #include <bits/stdc++.h>
    using namespace std;
    
    int T, M;
    int dp[1010]; // dp[j] 表示到当前为止花费 j 的时间的最大价值
    int t[110], v[110];
    
    void solve()
    {
        // 初始化
        for (int i = 0; i <= T; i++)
            dp[i] = 0;
    
        // 输入
        for (int i = 1; i <= M; i++)
            cin >> t[i] >> v[i];
    
        // 状态转移,dp[j] = max(dp[j], dp[j - t[i]] + v[i])
        for (int i = 1; i <= M; i++)
            // j 自右向左遍历,注意转移范围要保证 j - t[i] >= 0
            for (int j = T; j - t[i] >= 0; j--)
                dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
    
        // 输出,到最后花费 T 时间的最大价值
        cout << dp[T] << '\n';
    }
    
    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        while (cin >> T >> M)
        {
            if (T == 0 && M == 0)
                break;
            solve();
        }
        return 0;
    }

完全背包-无穷背包


  • 无穷背包

    1、无穷背包:给定容积为 m 的背包(不超过 105),有 n 种商品(不超过 500),每种商品价值为 w(不超过 109),体积为 v(不超过 m)。若商品数量无限可以重复放入同一商品,输出最多可以带走多少价值的物品
    2、与上一题不同,每件物品可以重复选择,是完全背包问题。运用动态规划的思想,先确定状态:令dp[i][j]表示到第 i 个物品为止用了 j 的容积所获得的最大价值
    3、再确定转移,对于当前的dp[i][j],有两种情况:如果没选择当前第 i 个物品,则dp[i][j] = dp[i-1][j](没有花费容积,没有增加价值,和上一个——到第 i-1 个物品的状态相同),此时直接标记dp[i][j],其相当于选择了 0 个第 i 个物品;如果选择了当前第 i 个物品,则dp[i][j] = dp[i][j-v[i]] + w[i](当前状态等同于dp[i][j-v[i]]当前行当前个数-1 个物品的价值 + 当前物品价值,其中因为当前dp[i][j]花费的总容积为 j,所以当前数量-1 个物品的容积应为j-v[i])
    4、最后确定初始化和边界初始化dp[0][i] = 0(到第 0 个物品无论花费多少容积,价值为 0);边界为 i <= n, j <= m
    5、由于朴素算法数组大小过大,所以栈空间不足,需要用滚动数组优化2 行的数组

  • 代码实现

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 510;
    const int A = 1e5 + 10;
    
    int m, n;       // 容积和商品种类
    int dp[N][A];   // 到第 i 个物品花费 j 容积的最大价值
    int w[N], v[N]; // 商品价值和体积
    
    void solve()
    {
        cin >> m >> n;
    
        // 初始化
        for (int i = 0; i <= m; i++)
            dp[0][i] = 0;
    
        // 输入
        for (int i = 1; i <= n; i++)
            cin >> w[i] >> v[i];
    
        // 状态转移
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (j - v[i] >= 0)
                    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][m] << '\n';
    }
    
    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T = 1;
        // cin >> T;
        while (T--)
            solve();
        return 0;
    }
  • 滚动数组优化

    #include <bits/stdc++.h>
    using namespace std;
    
    #define int long long
    const int N = 510;
    const int A = 1e5 + 10;
    
    int m, n;       // 容积和商品种类
    int dp[2][A];   // 到第 i 个物品花费 j 容积的最大价值
    int w[N], v[N]; // 商品价值和体积
    
    void solve()
    {
        cin >> m >> n;
    
        // 初始化
        for (int i = 0; i <= m; i++)
            dp[0][i] = 0;
    
        // 输入
        for (int i = 1; i <= n; i++)
            cin >> w[i] >> v[i];
    
        // 状态转移
        for (int i = 1; i <= n; i++)
        {
            // 滚动数组优化:当前行为 cur,上一行为 cur ^ 1
            int cur = i & 1;
    
            for (int j = 0; j <= m; j++)
            {
                if (j - v[i] >= 0)
                    dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - v[i]] + w[i]);
                else
                    dp[cur][j] = dp[cur ^ 1][j];
            }
        }
    
        // 输出,最后一行的 cur = n & 1
        cout << dp[n & 1][m] << '\n';
    }
    
    signed main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T = 1;
        // cin >> T;
        while (T--)
            solve();
        return 0;
    }

多重背包-多重背包


  • 多重背包

    1、多重背包:给定容积为 m 的背包,有 n 种商品(m,n 不超过 100),其中每种商品只有 s 件价值为 w体积为 v(都不超过 100)。若可以重复放入同一商品,输出最多可以带走多少价值的物品
    2、多重背包可以看作商品限量完全背包。对于每种商品有 s 件,可以将其展开为 s 件单独的只能选 1 次的商品,即如有 3 件商品 a,可看作有 3 个只能选 1 次的商品 a,此时即将其转化为01 背包解决
    3、实际实现中,并不会将展开的商品存储下来,而是读到一件商品,跑s[i]一维 01 背包。但注意,只适合数据量较小的情况

  • 代码实现

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 110;
    int dp[N]; // 一维 01 背包,到当前为止花费 j 容量的最大价值
    
    void solve()
    {
        int m, n;
        cin >> m >> n;
    
        for (int i = 1; i <= n; i++)
        {
            int s, w, v;
            cin >> s >> w >> v;
    
            // 执行 s 次 01 背包
            while (s--)
                // 一维 01 背包
                for (int j = m; j - v >= 0; j--)
                    dp[j] = max(dp[j], dp[j - v] + w);
        }
    
        // 输出到最后花费 m 容积的最大价值
        cout << dp[m];
    }
    
    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T = 1;
        // cin >> T;
        while (T--)
            solve();
        return 0;
    }
  • 二进制优化

    1、多重背包二周目:在上题基础上,n,m,s 范围改为不超过 2000
    2、由于原思路时间复杂度 O(n*m*s),一定超时。原先的拆分思路将 s 拆分s 个 1 相加,再来表示选择[0, s]个物品的情况(如 84 个商品相当于从中选 84 个 1 个商品相加表示)
    3、还可以用二进制拆分的方式优化,从二进制低位向高位拆分,剩余不够拆的放在最后,例如s = 116可拆分为s = 1 + 2 + 4 + 8 + 16 + 32 + 53,这样选择[0, s]个物品一定能够被这些数组合得到(如84 = 1 + 2 + 4 + 8 + 16 + 53),也可以达到原思路相同的效果
    4、此时执行01 背包时,可看作拆分出的商品打包在一起,如上s = 116时即对 1 个商品、2 个商品、4 个商品、8 个商品等进行选择(其 w,v 也乘以对应的系数 1,2,4,8)

    #include <bits/stdc++.h>
    using namespace std;
    
    #define int long long
    
    const int N = 2010;
    int dp[N]; // 一维 01 背包,到当前为止花费 j 容量的最大价值
    
    void solve()
    {
        int m, n;
        cin >> m >> n;
    
        for (int i = 1; i <= n; i++)
        {
            int s, w, v;
            cin >> s >> w >> v;
    
            vector<int> vec; // 记录 s 的拆分
            // 从二进制低位向高位拆分 s
            int x = 1;
            while (s >= x)
            {
                vec.push_back(x);
                s -= x;
                x <<= 1;
            }
            // 如果还有剩余,也加入 vec
            if (s)
                vec.push_back(s);
    
            // 从 vec 中取 k 作为系数,用于表示 [0, s] 之间的所有可能
            for (int &k : vec)
                // 一维 01 背包(注意范围,v 也要乘系数)
                for (int j = m; j - k * v >= 0; j--)
                    dp[j] = max(dp[j], dp[j - k * v] + k * w);
        }
    
        // 输出到最后花费 m 容积的最大价值
        cout << dp[m];
    }
    
    signed main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T = 1;
        // cin >> T;
        while (T--)
            solve();
        return 0;
    }

页底评论