關於各種背包問題

• 2020 年 5 月 22 日
• 筆記
• 經驗拾遺

概述

嗯……背包問題是什麼？

背包問題，是動態規劃問題中的典型的一類。顧名思義，是跟背包有關的問題（竟然和名字有關，爺青結）。

大概就是講背包空間有限，怎樣合理地裝物品可以讓總價值最高的問題。

其實也不是非常難。

本文講哪幾類？

背包問題的主要難點也就在於種類繁多，需要記憶各種遞推公式、循環結構。

不過畢竟是記憶而已，總是比其他需要現場推倒遞推公式的要好不少。

本文主要講以下幾類：

01背包問題

完全背包問題（目前只講前兩種，後面的以後慢慢更新，畢竟所有背包都是以這兩種為基礎的）（後面的題目已經寫好，以後講解）

多重背包問題

二維費用背包問題

分組背包問題

01背包問題

題目

題目描述

一個旅行者有一個最多能裝 MM 公斤的背包，現在有 nn 件物品，它們的重量分別是W1，W2，...,WnW1，W2，…,Wn,它們的價值分別為C1,C2,...,CnC1,C2,…,Cn，求旅行者能獲得最大總價值。

輸入

第一行：兩個整數，MM(背包容量，M≤200M≤200)和NN(物品數量，N≤30N≤30)；

第2..N+12..N+1行：每行二個整數Wi，CiWi，Ci，表示每個物品的重量和價值。

輸出

僅一行，一個數，表示最大總價值。

輸入樣例

10 4
2 1
3 3
4 5
7 9

輸出樣例

12

講解

既然要用用動態規劃法解決0-1背包問題，我們就先定義動態規劃的三個要點，即狀態、狀態轉移方程和邊界條件。

首先我們用子問題定義狀態，我們用F(i,j)表示「把前i件物品放入容量為j的背包中的最大總重量」。

然後我們要考慮怎樣的狀態轉移方程可以把這個問題轉化為更小的子問題。我們依然以「每一個物品都有放或不放兩種選擇」的策略為基礎，考慮第i件物品，如果我們選擇不放第i件物品，那麼問題就直接轉化為「把前i-1件物品放入容量為j的背包中的最大總重量」，如果我們選擇放第i件物品，那麼問題就轉化為「把前i-1件物品放入容量為j-V[i]的背包中的最大總重量加上第i件物品的重量」（這裡值得注意的一點是，如果j-V[i]<0，即放入第i件物品後超過了背包容量的限制，那麼我們就只能選擇不放第i件物品了）。所以狀態轉移方程為F(i,j)=max{F(i-1,j),F(i-1,j-V[i])+W[i]}。

邊界條件則很容易得到，i=0時F(i,j)為0（沒有物品就沒有重量），j<0時F(i,j)為負無窮（但在程式碼中並不會這樣初始化，我們在j-V[i]<0時不計算第二種情況即可）。最終答案則是f(n,C)。
但其實這個空間複雜度是可以優化的。

可以直接用f[i]來表示當重量為i時，可以有的最大價值。

狀態轉移方程：

f[j] = max(f[j], f[j-c[i]]+w[i])

到了這裡，終於要講循環順序的問題了。

其實第二層循環為什麼要反向的問題，我也研究了好久，終於在看一篇文章的時候恍然大悟。

根據題意，每種物品只有一件。

當我們循環的時候，如果正序，那自然就會從前到後的更新數組。

那如果背包容量大於某件物品的多倍呢？

而恰好這件物品性價比很高？

假設a是一個常數。這件物品的品質為w。

那麼，比如說，我們在循環到i=a的時候，把這件物品裝進了背包。

那再循環到i=a+w的時候，可能又會把這件物品裝進背包。

也就是說，這件物品被使用了兩次，甚至後面可能更多。

而根據題意，每件物品只有一個。

而對於每一次更新，只會用到i比當前小的數據，而不會用到i比當前大的。（因為要查看f[i-w[j]],w[j]不可能是負的）

所以，先把大的更新了是沒有問題的。

（學了背包問題這麼久，終於把這個問題解決了！！！開心！！！）

核心程式碼：

#include <iostream>
#include <cstdio>
#define M 1000

using namespace std;

int f[M], c[M], w[M];
int ans, v, m;

int main() 
{
    scanf("%d%d", &v, &m);
    for(int i = 1; i <= m; i++)
    { 
        scanf("%d%d", &c[i], &w[i]);
    } 
    for(int i = 1; i <= m; i++)
    { 
        for(int j = v; j >= c[i]; j--) 
        {
            f[j] = max(f[j], f[j-c[i]]+w[i]);
        }
    } 
    printf("%d\n", f[v]);
    return 0;
}

完全背包問題

題目

題目描述

設有nn種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為MM，今從nn種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小於等於MM，而價值的和為最大。

輸入

第一行：兩個整數，MM(背包容量，M≤200M≤200)和NN(物品數量，N≤30N≤30)；

第2..N+12..N+1行：每行二個整數Wi,CiWi,Ci，表示每個物品的重量和價值。

輸出

僅一行，一個數，表示最大總價值。

輸入樣例

10 4
2 1
3 3
4 5
7 9

輸出樣例

max=12

#include <iostream>
#include <cstdio>
#define M 1000

using namespace std;

int f[M], c[M], w[M];
int ans, v, m;

int main() 
{
    scanf("%d%d", &v, &m);
    for(int i = 1; i <= m; i++)
    { 
        scanf("%d%d", &c[i], &w[i]);
    } 
    for(int i = 1; i <= m; i++)
    { 
        for(int j = c[i]; j <= v; j++) 
        {
            f[j] = max(f[j], f[j-c[i]]+w[i]);
        }
    } 
    printf("max=%d\n", f[v]);
    return 0;
}

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

1040

#include <bits/stdc++.h>
#define M 1000

using namespace std;

int f[M], c[M], w[M],num[M];
int ans, v, m;

int main()
{
        scanf("%d%d", &v, &m);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &c[i], &w[i],&num[i]);
        }
        int jjc=m;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= num[i]; ++j)
            {
                c[jjc]=c[i];
                w[jjc]=w[i];
                jjc++;
            }
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = c[i]; j <= v; j++)
            {
                f[j] = max(f[j], f[j-c[i]]+w[i]);
            }
        }
        printf("max=%d\n", f[v]);
        return 0;
}

10 100 5
7 10
2 40
2 50
1 20
4 20

3 30

10 100 5

8 110

12 10

20 10

5 200

1 110

0 100

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

20