說說01背包和二分

• 2021 年 10 月 21 日
• 筆記
• 學習, 題解

title: “01背包與二分”
author: Sun-Wind
date: October 21, 2021

本帖背景：最近博主在練習01背包的問題，發現一道題結合了01背包和二分算法，令本蒟蒻大受啟發，特此來水一篇分享

Knowledge reserve（知識儲備）

01背包

經典的01背包問題是給定一定數量的物品和限定大小的背包，每個物品有一定的價值，要求在不超過背包容量的情況下最多能裝多少價值的物品

我們先給出一般化的二維背包方程dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])

• dp[i][j]所表達的含義是在已經考慮了前i-1個物品的情況下，考慮第i個物品背包容量為j時的最大價值
• w[i]表示第i個物品的容量（weight），v[i]表示第i個物品的價值（val）
• 此遞推方程的實質是把背包分割成從0~背包容量的很多個小部分，這樣做可以兼顧到所有的情況
• 遞推方程的含義是第i個物品容量為j時的最大價值是 第i-1個物品容量為j時的最大價值 和 第i-1個物品容量為j-w[i]時的最大價值加上第i個物品的價值 這兩個中的最大價值（實際上就是選第i個物品和不選第i個物品兩種情況）

關於遞推方程的思考，我們可以這樣想

假如有3個物品，背包容量為8 物品的重量和價值分別為3,6 4,7 5,8
當我們循環到第二個物品是dp[2][8]就是把兩個物品都考慮進去價值為13
但是當我們循環到第3個物品時背包的容量不夠，但由於把這個物品放入背包仍然屬於一種情況
為了不漏解dp[3][8] = max(dp[2][8],dp[2][8-5] + 8)
我們在這裡把背包進行分割，顯然背包容量為3時我們把物品1放入了背包，從這部分背包遞推到背包容量為8時的情況是最優解

其他的情況也可以同樣類比，這樣我們既能把每一種情況都考慮到又可以找到最優的解
核心代碼如下

 for(i = 1; i <= m; ++i)//枚舉個數
        for(j = 1; j <= n; ++j)//枚舉容量
    {
        if(w[i] <= j)
        dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]);
        else
        dp[i][j] = dp[i - 1][j];
    }

好扒，先給你5分鐘思考的時間我們再繼續

• 1
• 2
• 3
• 4
• 5

01背包空間的優化

接下來我們考慮把01背包的二維數組從二維優化到1維
核心dp[i][j] -----> dp[j]
dp[j] = max(dp[j],dp[j-w[i]] + v[i])

• 優化過後的1維數組表示背包容量為j時所能得到的最大價值
• w[i],v[i]和上述例子相同
• 這裡的遞推是由上一狀態（即只考慮前i-1個物品）背包容量為j的最大價值推到這一狀態（開始考慮第i個物品容量為j時的最大價值
  根據二維數組的代碼我們可以自然的帶過來

for(i = 1; i <= m; ++i)
      for(j = 1; j <= n; j--)
    {
        if(w[i] <= j)
        dp[j] = max(dp[j],dp[j - w[i]] + v[i]);//這裡dp[j]儲存的是上一狀態
    }

嗯，不錯，大部分都是正確的，但還需要注意一點————————循環順序

試着思考正序循環我們可能會面臨這樣一個問題，如果背包中原本有個物品重量為k的物品，當j = k的時候，我們會面臨是否將這個特殊的物品放入背包，
而當j為2k的時候我們將會面臨同樣的選擇
如果在兩次選擇中我們都發現把這個物品放入背包的價值更大，接下來會發生什麼？
顯然我們把一個物品放入了兩次，但是一個物品只能放入一次，和題意不符

所以我們需要把循環順序顛倒一下，代碼如下：

    for(int i = 0;i < n;i ++){
        int v, w;
        cin >> v >> w;
        for(int j = V;j >= v;j --)//顯然如果j<v的時候就不用放入此物品，因此也就不用更新循環
            dp[j] = max(dp[j], dp[j - v] + w);//max中的兩種狀態都是上一個狀態
    }
    cout << dp[V];

01背包的講解就到這裡就結束了，01背包還有很多擴展比如多重背包，完全背包等等，這裡暫時不去討論這些

接下來我們看看其他的

二分

在臨界點左邊的所有數都滿足或不滿足某一條件，右邊的數都不滿足或滿足某一條件（也就是跟之前的相反）

• 顧名思義，二分就是不斷地尋找中間的值，不斷地逼近我們想要的答案
• 下面給出一個大致的模板（具體的可能會根據題目的要求有所變化）

 while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid))//檢驗中間的值是否滿足要求
                l = mid + 1;
            else
                r = mid;
        }

下面給出這樣的一個例子來幫助我們理解
給定一組數字 1 2 3 3 4 5共6個數字，要求找到第一個大於等於3的數字
顯然這個數組滿足我們的先決條件，一部分小於3，一部分不小於3。
根據二分算法的性質我們理論上可以找到這個臨界點

我們的答案在1~6中選取，（這裡指的是各個數的編號）,所以l左邊界就是1，r右邊界是6。
第一次mid是3，第3個數滿足要求，所以但是由於要找第一個數，此時這個數可能是第一個也可能不是，所以右邊界要變成mid；然後再繼續判斷直到找到我們想要的臨界值

好了，現在我們有了一定的知識儲備，可以來看一道01背包和二分結合的例子：

例題

本題來源於洛谷P2370（看懂了可以自行去ac）

題目描述

你找 yyy2015c01 借到了這個高端的 U 盤，拷貝一些重要資料，但是你發現這個 U 盤有一些問題：

• 這個 U 盤的傳輸接口很小，只能傳輸大小不超過 L 的文件。
• 這個 U 盤容量很小，一共只能裝不超過 S 的文件。
  但是你要備份的資料卻有很多，你只能備份其中的一部分。

為了選擇要備份哪些文件，你給所有文件設置了一個價值 Vi，你希望備份的文件總價值不小於 p。

但是很快你發現這是不可能的，因為 yyy2015c01 的傳輸接口太小了，你只有花錢買一個更大的接口（更大的接口意味着可以傳輸更大的文件，但是購買它會花費更多的錢）。

注意：你的文件不能被分割（你只能把一個文件整個的傳輸進去，並儲存在U盤中）,

你放在 U 盤中文件的總大小不能超過 U 盤容量。

現在問題來了：你想知道，在滿足 U 盤中文件價值之和不小於 p 時，最小需要多大的接口。

輸入格式

第 1 行，三個正整數 n,p,S 分別表示文件總數，希望最小价值 p ，硬盤大小。

接下來 n 行，每行兩個正整數 Wi,Vi
​表示第 i 個文件的大小和價值。

輸出格式

輸出一個正整數表示最小需要的接口大小。

如果無解輸出 No Solution!。

輸入

3 3 5
2 2
1 2
3 2

輸出

2

輸入

2 3 505
1 2
500 1

輸出

500

輸入

3 3 2
2 2
1 2
3 2

輸出

No Solution!

輸入

4 5 6
5 1
5 2
5 3
1 1

輸出

No Solution!

思路解析

通過題目中的關鍵詞比如限定了大小，價值等因素可以初步判斷可能是一個01背包的問題，但是由於題目中還給了另外一個因素就是要求所得得價值必須超過所給得價值，而且我們還要找一個最小的接口
這些信息給了我們很大的混淆

• 首先我們要先確定這次的01背包所代表的信息是什麼
  是最小的接口，是最大的價值？？？

我們每次選完形成的一種選法所得的接口大小是背包中所有接口的最大大小，然後我們還要把這所有符合要求的選法選出來，從這些接口中找到一個最小的，如果考慮表示最小的接口，顯然維護起來非常困難，而且由於題目所給的價值數很大，難以用數組儲存

• 如果表示最大的價值，我們應該怎麼做？
  要說明一點的是題目中我們可以得出這是一個最大值最小的問題，而這是一個很經典的二分關鍵詞。

我們能從剛開始的輸入中知道所有的端口，而正確答案的端口一定會在這個區間之間。但是題目所給的端口不一定是來連續的。比如三個端口80，90，100；我們只知道答案是這三個端口中的一個，但並不是81，82等等；因此我們設置二分元素是正確答案小於等於我們所二分的端口大小。
這樣做的話顯然二分區間會出現一個臨界點,而臨界點左邊不滿足二分的要求，臨界點的右邊滿足二分的要求
所以我們只需要二分這個區間，進而去逼近答案

 while (minn < maxx)
    {
        midd = minn + maxx >> 1;
        if (dp(midd) >= m)//dp函數詳情請繼續往下看解析
            maxx = midd;
        else
            minn = midd + 1;//minn和maxx分別是左右邊界
    }

因此我們需要每次判斷時都對這個端口做一次01背包，如果有比他大的端口一定不選（因為選了的話最大的端口就會發生改變），

int dp(int x)
{
    for(int i = 0; i <= s; ++i)
        Matrix[i] = 0;
    for(int i = 1; i <= n; ++i)
    {
        if (x != -1 && x < w[i])//如果碰到比他大得就不考慮，這裡特殊一種-1得情況是為了判定是否有解，-1得情況就是求這個背包在沒有限制條件下得最大價值
            continue;
        for (int j = s; j >= w[i]; --j)
            Matrix[j] = max(Matrix[j], Matrix[j - w[i]] + v[i]);
    }
    return Matrix[s];
}

小於等於它的就可以放入背包中。只要存在一種解法，能夠使得所選方案湊出來的價值數大於題目所給的價值數，那麼顯然這個端口是滿足要求的，右區間向前移動，（如果我們已知小於等於x的端口能湊出滿足題意得價值，那麼大於x得數一定會包含x得這種方案，因此後面01背包求出來得價值只有可能比他高）

• 我們得整個解題思路就這樣形成了
  下面貼上完整得代碼

#include <iostream>
#include <utility>
using namespace std;
typedef long long ll;
#define fi(a, b) for (int i = a; i <= b; ++i)
#define fr(a, b) for (int i = a; i >= b; --i)
using pii = pair<int, int>;
const int N = 1e3 + 5;
const int M = 1e5 + 5;
int w[N], v[N];
int n, m, s;
int Matrix[M];
//#define DEBUG
int dp(int x)
{
    fi(0, s)
        Matrix[i] = 0;
    fi(1, n)
    {
        if (x != -1 && x < w[i])
            continue;
        for (int j = s; j >= w[i]; --j)
            Matrix[j] = max(Matrix[j], Matrix[j - w[i]] + v[i]);
    }
    return Matrix[s];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef DEBUG
    //freopen(D:\in.txt,r,stdin);
#endif
    cin >> n >> m >> s;
    int minn = 0x3f3f3f3f;
    int maxx = -minn;
    fi(1, n)
    {
        cin >> w[i] >> v[i];
        minn = min(minn, w[i]);
        maxx = max(maxx, w[i]);
    }
    int midd;
    while (minn < maxx)
    {
        midd = minn + maxx >> 1;
        if (dp(midd) >= m)
            maxx = midd;
        else
            minn = midd + 1;
    }
    if (dp(-1) < m)
        cout << "No Solution!" << endl;
    else
    {
        cout << minn << endl;
    }
    return 0;
}

順便貼上博主得一些hack樣例（之前用二維背包只能騙70分┭┮﹏┭┮）
input

13 62 124
20 13
20 19
20 13
34 13
49 133
43 1
20 22
20 30
36 30
36 4
42 13
37 11
44 1
37 16
21 10
36 19
49 27
27 5
24 11
23 13
50 25
44 27
37 12
48 1

output
20
input

840 269 909
108 240
978 297
474 362
999 994
121 72
704 261
300 285
281 239
882 563
486 972
933 295
131 280
741 374
457 78
44 15
45 12
870 749
331 843
53 61
241 584
76 195
522 955
910 695
877 917
737 228
256 443
357 4
229 98
487 648
352 416
363 559
136 205
880 634
508 874
61 136
730 78
861 203
420 919
692 605
60 96
789 809
670 301
242 923
994 586
849 700
750 483
461 615
738 944
474 897
610 953
759 303
260 579
681 347
302 741
754 119
383 253
860 251
484 340
451 93
176 592
960 711
817 462
477 429
564 598
748 728
684 889
987 590
927 826
881 759
544 339
581 728
263 535
662 217
878 823
778 378
442 246
101 44
307 217
115 349
182 68
980 132
895 300
564 407
445 147
354 447
705 595
171 58
674 617
589 594
758 366
632 779
130 170
153 478
547 37
642 860
129 164
790 364
74 168
565 997
939 220
478 651
135 80
872 671
253 421
664 473
109 136
491 675
120 106
225 464
660 403
491 428
509 462
640 847
920 112
496 168
73 176
127 204
567 341
570 578
393 156
873 286
647 627
193 282
1000 154
648 910
465 868
837 54
629 488
940 953
264 740
417 483
159 417
960 748
656 146
200 253
611 125
61 16
858 559
866 102
566 6
720 357
973 364
725 259
883 461
234 259
520 780
176 642
409 352
31 0
926 231
710 606
48 88
202 427
566 956
607 666
125 388
129 85
535 907
172 707
921 456
971 336
817 484
373 157
597 923
454 918
786 754
63 31
980 719
257 132
331 665
952 522
644 88
506 388
517 446
339 651
571 770
751 629
866 914
390 953
676 441
194 379
203 284
55 38
142 174
261 89
617 332
321 11
156 490
699 994
109 316
528 210
569 416
391 761
416 759
400 441
435 56
272 401
531 746
288 381
509 987
376 34
395 274
589 728
730 462
677 494
698 854
916 299
950 672
542 231
792 770
680 355
918 456
898 517
953 336
959 531
90 210
152 436
281 665
265 143
535 742
721 651
411 365
403 880
924 614
358 971
495 814
261 442
983 910
988 325
200 372
310 898
304 412
212 25
1000 831
527 302
243 247
455 566
218 520
576 800
305 580
481 143
735 553
933 293
276 621
92 22
573 843
156 183
533 156
66 111
420 565
777 52
911 162
210 692
721 516
761 407
381 259
903 361
901 663
990 467
848 231
881 5
585 870
949 501
707 607
230 18
183 544
142 405
637 804
229 103
587 1
204 49
994 100
456 854
598 165
529 564
217 174
981 578
244 147
710 629
184 751
713 779
129 316
164 157
758 766
634 456
136 27
83 133
538 559
363 691
476 566
739 743
642 912
446 988
746 949
924 833
344 634
811 197
594 859
930 371
335 66
889 154
81 71
658 843
692 648
672 21
689 975
485 694
270 244
56 10
553 209
414 924
565 781
908 788
702 423
967 429
915 40
183 468
112 95
591 793
255 392
891 245
757 69
688 679
643 446
342 715
779 573
458 937
192 150
75 118
727 924
542 282
177 115
709 524
769 105
47 17
319 407
455 726
956 455
720 405
969 880
842 650
473 583
755 389
848 329
972 961
602 27
854 182
885 746
362 161
347 568
675 926
464 553
555 675
36 24
901 141
816 763
982 834
341 481
94 87
528 510
747 727
576 393
468 918
285 452
993 764
87 131
951 170
485 984
62 85
881 844
74 131
529 3
669 498
796 861
535 798
527 337
299 939
802 143
863 398
74 118
190 191
236 881
828 637
417 258
790 533
739 291
89 122
355 52
272 209
84 132
816 342
871 560
158 283
173 508
229 936
577 899
242 631
389 848
165 152
486 182
488 260
750 574
378 546
576 397
698 109
425 864
62 0
505 443
836 364
929 2
162 598
288 874
278 329
324 728
813 644
472 779
196 408
708 291
821 657
202 324
178 3
98 256
382 660
793 849
603 297
843 200
429 403
216 396
902 852
508 343
687 528
68 91
906 84
797 714
347 624
915 217
109 297
845 281
129 256
546 77
856 273
173 580
863 539
297 327
904 537
648 449
862 791
133 264
285 196
679 273
869 539
545 205
817 787
767 222
929 499
989 930
789 576
969 508
593 624
504 326
408 172
888 778
231 69
248 509
393 213
366 616
965 308
536 319
100 87
846 838
304 704
226 442
895 491
756 338
458 494
150 17
295 496
962 671
59 98
738 962
366 461
231 69
762 280
287 361
355 724
592 344
861 289
339 988
600 970
294 115
806 951
412 284
536 466
630 962
669 965
71 205
402 105
523 651
697 912
543 528
927 189
742 580
185 256
445 669
938 902
979 884
814 149
922 533
668 425
983 413
648 954
883 547
999 484
991 160
475 906
482 132
468 331
82 231
789 22
439 547
238 325
221 778
138 517
272 380
292 44
622 832
775 316
425 385
250 231
411 316
795 589
868 499
409 616
46 54
299 905
85 252
387 282
518 566
488 518
416 570
328 249
924 154
542 117
721 867
626 99
123 61
577 826
173 14
721 881
473 679
168 438
544 858
126 119
246 87
915 52
562 189
787 126
456 210
361 77
810 320
594 537
955 16
375 601
53 107
777 139
569 835
179 436
506 80
96 323
119 220
331 540
898 11
492 413
359 798
214 16
960 366
179 62
857 448
461 867
562 923
511 66
952 280
743 742
640 361
807 936
981 858
164 521
374 841
699 149
174 161
484 231
644 736
908 23
558 35
129 404
758 666
927 210
533 958
507 375
851 338
571 6
432 256
205 318
317 434
540 236
219 722
475 113
264 898
30 0
306 235
634 797
469 398
86 243
610 914
650 0
915 376
151 422
74 84
970 12
43 62
966 115
693 533
904 495
649 123
469 449
702 119
529 970
92 261
55 89
240 345
226 800
746 907
970 167
561 202
573 423
356 116
456 17
806 962
267 577
113 136
463 0
903 767
355 527
95 247
222 44
459 658
714 571
101 80
364 895
897 468
364 169
934 952
190 495
165 468
284 946
647 390
643 250
52 57
457 969
475 462
769 501
304 957
288 600
679 364
225 804
600 208
233 241
342 13
110 261
720 518
225 752
585 469
143 242
357 532
297 341
942 846
310 56
904 822
482 689
773 100
446 350
276 178
384 717
937 581
162 161
267 637
394 596
42 21
764 353
736 539
870 875
616 721
250 900
353 718
147 512
415 499
127 266
194 416
940 903
621 161
228 114
521 188
225 109
902 86
268 169
89 152
507 619
193 72
197 488
554 266
540 715
538 49
320 780
544 685
483 467
763 868
424 161
967 615
693 325
447 990
901 490
756 825
714 806
881 303
556 625
589 637
86 220
227 320
320 262
148 6
987 617
853 797
916 546
606 704
945 574
286 749
908 875
98 221
227 934
247 931
588 706
33 0
347 945
126 346
210 663
988 976
267 146
660 676
514 539
708 518
979 628
309 753
647 715
628 967
455 644
251 117
729 843
696 713
270 352
313 906
925 954
171 462
182 443
681 867
58 89
619 469
850 364
860 848
654 651
886 715
326 639
119 440
86 121
675 0
682 297
305 475
342 872
604 97
178 249
455 780
70 96
857 280
145 207
690 78
396 147
621 338
277 520
306 177
97 48
526 133
953 760
177 268
750 558
74 55
382 748
155 568
836 121
638 468
822 369
720 597
44 17
130 219
531 700
582 16
402 196
367 868
201 46
52 24
559 224
514 139
990 811
664 271
165 299
81 112
783 111
450 0
932 398
510 169
576 16
279 216
378 26
637 43
204 745
502 25
426 832
166 123
834 946
235 735
926 250
840 699
724 704
777 806
59 14
609 493
666 128
976 52
897 0
191 103
443 868
53 56

output
48
今天的分享就到這裡，感謝大家來拜訪本蒟蒻的帖子~~