寒假训练——第三周（背包DP）

A - CD

思路：

背包问题求具体方案（不能化二维为一维）
要求按照顺序打印答案，我们则反向枚举，输出 $f [1] [m]$ 为答案

类似与，最短路求路径
如图所示：
在这里插入图片描述
即，g[i][j]记录上一层的路径，直接返回上一层
又因为，题目要求按照顺序输出，我们如果直接按照f[n][m]输出，输出的为反向路径，如此我们仅需将f[n][0]作为起点将f[1][m]作为终点，如此即为顺序输出

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 50, M = 1e5 + 10;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f[50][M];
int v[N];

void solve()
{
    memset(f, 0, sizeof f);
    memset(v, 0, sizeof v);
    
    for (int i = 1; i <= n; i ++ )
        cin >> v[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]] + v[i]);
        }
    }
    
    int j = m;
    for (int i = 1; i <= n; i ++ )
        if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + v[i])
        {
            cout << v[i] << " ";
            j -= v[i];
        }
    
    cout << "sum:"<< f[1][m] << endl;
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    //cin >> T;
    
    while(cin >> m >> n)
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

B - Piggy-Bank

思路：

完全背包

注意：

要求恰好为该体积

可见如下博客：体积的各种情况划分
背包问题中体积至多是 j ，恰好是 j ，至少是 j 的初始化问题的研究

三维形式：TLE
二维形式：MLE
只能写一维了，，

二维代码参考：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 510, M = 10010;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f[N][M];
int v[N], w[N];

void solve()
{
    int m0;
    memset(f, 0x3f, sizeof f);
    cin >> m0 >> m;
    cin >> n;
    m -= m0;
    
    for (int i = 1; i <= n; i ++ )
        cin >> w[i] >> v[i];
    
    f[0][0] = 0;
    
    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] = min(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }
    
    if(f[n][m] == LL_INF) cout << "This is impossible." << endl;
    else cout << "The minimum amount of money in the piggy-bank is " << f[n][m] << "." << endl;
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

一维AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 510, M = 10010;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f[M];
int v[N], w[N];

void solve()
{
    int m0;
    memset(f, 0x3f, sizeof f);
    cin >> m0 >> m;
    cin >> n;
    m -= m0;
    
    for (int i = 1; i <= n; i ++ )
        cin >> w[i] >> v[i];
    
    f[0] = 0;
    
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = v[i]; j <= m; j ++ )
            f[j] = min(f[j], f[j - v[i]] + w[i]);
    }
    
    if(f[m] == LL_INF) cout << "This is impossible." << endl;
    else cout << "The minimum amount of money in the piggy-bank is " << f[m] << "." << endl;
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

C - Coins（男人八题）

C - Coins

思路：

多重背包问题（特殊单调队列优化）

注：二进制优化 $T L E$

朴素代码如下：

    f[0][0] = 1;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]]);
1
2
3
4
5

我们可以发现：

f[i][j]只与i-1层的一段状态有关，如此我们用数组g表示i-1的此段中离j最近的距离（单位距离为v[i]），如此我们可在O(1)的情况下找到f[i][j]是否符合条件。

多重背包优化 代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 1010, M = 100010;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

bool f[M];
int g[M]; // 距离 f[j] 最近位置的 1
int v[N], cnt[N];

void solve()
{
    memset(f, 0, sizeof f);
    
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &v[i]);
    
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &cnt[i]);
    
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        memset(g, 0, sizeof g);
        for (int j = v[i]; j <= m; j ++ )
            if(!f[j] && f[j - v[i]] && g[j - v[i]] < cnt[i])
            {
                f[j] = 1;
                g[j] = g[j - v[i]] + 1;
            }
    }
    
    int res = 0;
    for (int i = 1; i <= m; i ++ )
        if(f[i]) res ++;
    
    printf("%d\n", res);
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    //cin >> T;
    
    while(scanf("%d %d", &n, &m), n || m)
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

D - 动态规划之分组背包

思路：

优先队列，，与DP没什么关系

E - Balance

思路：

背包模型，类似分组背包

具体做法：

因为重量为 -15*20*25 ~ +15*20*25之间，为-7500 ~ + 7500，定义平衡度为右边减去左边，则当平衡度为0时，即为平衡，平衡度含负数不利于数组表示，加7500偏移量，当平衡度为7500时，为平衡状态
f[i][j]表示只装前i个物品时，平衡度为j的状态
闫氏DP分析法：

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
//#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 25, M = 15010;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f[N][M];
int cnt[N], w[N];

void solve()
{
    cin >> m >> n;
    
    for (int i = 1; i <= m; i ++ )
        cin >> cnt[i];
    for (int i = 1; i <= n; i ++ )
        cin >> w[i];
    
    memset(f, 0, sizeof f);
    
    f[0][7500] = 1;
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < M; j ++ )
            for (int k = 1; k <= m; k ++  )
                f[i][j] += f[i - 1][j - cnt[k] * w[i]];
    
    cout << f[n][7500] << endl;
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

F - The Fewest Coins

思路：

多重背包 + 完全背包

具体步骤：

先找最大体积 maxv
多重背包求付钱的最小数量
完全背吧求找钱的最小数量
最后找二者相加的最小数量

找最大体积：（鸽巢原理又称抽屉原理）

给钱上界为：m + maxValue ^ 2，其中 maxValue为最大硬币面值。
证明： 反证法。
假设存在一种支付方案，John给的钱超过 m + maxValue ^ 2，
则售货员找零超过maxValue ^ 2，则找的硬币数目超过maxValue个，将其看作一数列，
求前n项和sum(n)，根据鸽巢原理，至少有两个对maxValue求模的值相等，
假设为sum(i)和sum(j),i，则i+1...j的硬币面值和为maxValue的倍数，同理，John给的钱的数量(最少为maxValue + m / maxv)中也有一定数量的硬币面值和为maxValue的倍数，
总结一下（通俗的讲）：店员把你的钱原封不动的找给你了，这无意义嘛，，

 
代码如下： 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 10010, M = 20010;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f1[M], f2[M]; // 恰好等于 j 的金币的最小数量
int cnt[N], w[N];
PII goods[M];

void solve()
{
    int idx = 0;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    
    // 多重背包二进制优化，求最少金币数量
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &cnt[i]);
        for (int k = 1; k <= cnt[i]; k *= 2)
        {
            cnt[i] -= k;
            goods[idx ++ ] = mkpr(k * w[i], k);
        }
        if(cnt[i] > 0) goods[idx ++ ] = mkpr(cnt[i] * w[i], cnt[i]);
    }
    
    memset(f1, 0x3f, sizeof f1);
    f1[0] = 0;
    
    for (int i = 0; i < idx; i ++ )
        for (int j = 20000; j >= goods[i].x; j -- )
            f1[j] = min(f1[j], f1[j - goods[i].x] + goods[i].y);
    
    // 完全背包，求找零最小数量
    memset(f2, 0x3f, sizeof f2);
    f2[0] = 0;
    
    for (int i = 1; i <= n; i ++ )
        for (int j = w[i]; j <= 20000; j ++ )
            f2[j] = min(f2[j], f2[j - w[i]] + 1);
    
    int res = INF;
    for (int i = m; i <= 20000; i ++ )
        res = min(res, f1[i] + f2[i - m]);
    
    if(res >= INF) printf("-1\n");
    else printf("%d\n", res);
    
    return;
}

signed main()
{
    //fast;
    T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95 
G - A Mini Locomotive 
G - A Mini Locomotive 
思路： 
01背包 
具体实现； 
对物品重新定义：第i个物品为：以第i个物品结尾的包含d个（含第i个物品）的物品总价值
状态表示：f[i][j]在前i个物品中选，并且选了j个互不冲突的物品的最大值
闫氏DP分析法：
  
代码如下： 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 50010, M = 5;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f[N][M]; // 只装前i个物品(以 i 结尾的 d 个物品)，且装了j车的最大价值
int sv[N], d; // sv数组，物品价值的前缀和

void solve()
{
    memset(f, 0, sizeof f);
    memset(sv, 0, sizeof sv);
    
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        sv[i] = sv[i - 1] + x;
    }
    cin >> d;
    
    for (int i = d; i <= n; i ++ )
        for (int j = 3; j >= 1; j -- )
            f[i][j] = max(f[i - 1][j], f[i - d][j - 1] + sv[i] - sv[i - d]);
    
    cout << f[n][3] << endl;

    return;
}

signed main()
{
    //fast;
    T = 1;
    cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73 
 
H - Armchairs 
H - Armchairs 
思路： 
线性DP
闫氏DP分析法
  
代码如下： 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 5010, M = 5;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

int f[N][N];
int peo[N], idx1;
int chair[N], idx2;

void solve()
{
    cin >> n;
    
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        if(x) peo[ ++ idx1] = i;
        else chair[ ++ idx2] = i;
    }
    
    for (int i = 1; i <= idx1; i ++ )
        for (int j = i; j <= idx2; j ++ )
        {
            f[i][j] = f[i - 1][j - 1] + abs(peo[i] - chair[j]); // 直接坐
            if(i < j) f[i][j] = min(f[i][j], f[i][j - 1]); // 不坐 (i == j) 时, 只能坐
        }
        
    cout << f[idx1][idx2] << endl;

    return;
}

signed main()
{
    //fast;
    T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75



                

                    相关阅读:

                    
mysql中GROUP_CONCAT函数详解                            

一个月涨粉5W，自媒体最不愿公开的5个免费工具                            

运行 `npm install` 时的常见问题与解决方案                            

Kruskal重构树 学习笔记                            

AWS的虚拟化技术                            

polygon yolo                            

Go入门简介                            

「PHP系列」数组详解                            

Web APIs——焦点事件以及小米搜索框                            

操作系统底层工作原理                            

                    
                
                
                    原文地址：https://blog.csdn.net/m0_61409183/article/details/126521274



        
            
                
                    最新文章
                
                
                    
攻防演习之三天拿下官网站群                            

数据安全治理学习——前期安全规划和安全管理体系建设                            

企业安全 | 企业内一次钓鱼演练准备过程                            

内网渗透测试 | Kerberos协议及其部分攻击手法                            

0day的产生 | 不懂代码的"代码审计"                            

安装scrcpy-client模块av模块异常，环境问题解决方案                            

leetcode hot100【LeetCode 279. 完全平方数】java实现                            

OpenWrt下安装Mosquitto                            

AnatoMask论文汇总                            

【AI日记】24.11.01 LangChain、openai api和github copilot                            

                    
                
            

            
                
                    热门文章
                
                
                    
十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧！！！                            

奉劝各位学弟学妹们，该打造你的技术影响力了！                            

五年了，我在 CSDN 的两个一百万。                            

Java俄罗斯方块，老程序员花了一个周末，连接中学年代！                            

面试官都震惊，你这网络基础可以啊！                            

你真的会用百度吗？我不信 — 那些不为人知的搜索引擎语法                            

心情不好的时候，用 Python 画棵樱花树送给自己吧                            

通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难，连憨憨学妹都学会了！                            

13 万字 C 语言从入门到精通保姆级教程2021 年版                            

10行代码集2000张美女图，Python爬虫120例，再上征途

寒假训练——第三周（背包DP）

目录

A - CD

B - Piggy-Bank

C - Coins（男人八题）

D - 动态规划之分组背包

E - Balance

F - The Fewest Coins

G - A Mini Locomotive

H - Armchairs