分组背包问题与背包问题求具体方案(一)

简介: AcWing算法提高课内容,本文讲解 动态规划

前言

AcWing算法提高课内容,本文讲解 动态规划

本篇包括以下题目:

⭐️ AcWing 12. 背包问题求具体方案

⭐️ AcWing 9. 分组背包问题

⭐️ AcWing 1013. 机器分配

⭐️ AcWing 734. 能量石


写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵


本文需要先自修基础:背包问题


注:本文中的所有代码全部为优化后的代码,且不提供优化解释,解释请见:背包问题,其中有详细的解释

背包问题求具体方案

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。

物品编号范围是 1 … N 。

数据范围:

image.png

输入样例:

4 5
1 2
2 4
3 4
4 6

输出样例:

1 4

思路分析

注意,因为要求输出的顺序是按照字典序,故我们在进行dp的过程中,枚举样本需要从大到小枚举,这样我们在按照字典序输出的时候就可以正向循环,查看状态i是由哪个状态j转移而来的 ( j > i )

代码

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

分组背包问题

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一个整数,表示最大价值。

数据范围:

image.png

输入样例:

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例:

8

思路分析

裸题,不解释,解释见博客:背包问题

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ ) 
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j; j -- )
            for (int k = 1; k <= s[i]; k ++ )
                if (v[i][k] <= j) 
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;
}




目录
相关文章
|
6月前
|
算法 JavaScript
class074 背包dp-分组背包、完全背包【算法】
class074 背包dp-分组背包、完全背包【算法】
48 0
|
6月前
多重背包和分组背包
多重背包和分组背包
|
1月前
|
C语言
末谈背包问题求具体方案
末谈背包问题求具体方案
|
6月前
|
算法
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
47 0
算法系列--动态规划--背包问题(2)--01背包拓展题目(下)
|
6月前
|
算法
算法系列--动态规划--背包问题(2)--01背包拓展题目(上)
算法系列--动态规划--背包问题(2)--01背包拓展题目
48 0
|
人工智能 算法 决策智能
动态规划之背包问题(01背包问题、完全背包问题、方案数填满型背包问题)
动态规划之背包问题(01背包问题、完全背包问题、方案数填满型背包问题)
248 1
|
算法 C语言 C++
【动态规划】多重背包问题,分组背包问题
与完全背包问题不同的是,每种东西都是有限件,前两种状态就不再过多赘述
147 4
动态规划——多重背包、分组背包
动态规划——多重背包、分组背包
62 0
动态规划:分组背包问题
动态规划:分组背包问题
87 0