背包問題(未完待續。。。)

背包問題

詞義：給定一組物品，每種物品都有自己的重量和價格。在限定的總重量内，如何選擇，才能使得物品的總價格最高。

分類:

• 01背包
• 多重背包
• 完全背包

先來講01背包(基礎 -> 優化)

截我回目錄

例題：分蛋糕

基礎思路：

乍一看，沒啥思路。。。

提示：

為了盡量的是他們兩人手中的蛋糕重量總和的內插補點最小，我們就可以讓其中某一個人的蛋糕重量正好達到 s u m / 2 sum / 2 sum/2(總重量的一半)。

然後這就變成了一個01背包問題：放？還是不放？？？

轉化後的思路：

先擷取 d p [ i ] [ j ] dp[i][j] dp[i][j]的狀态: 表示第i個數能不能正好放進容量為j的背包中

确定轉移方程: i f ( d p [ i − 1 ] [ j − v [ i ] ] ( 取 ) ∣ ∣ d p [ i − 1 ] [ j ] ( 不 取 ) ) if(dp[i - 1][j - v[i]] (取) || dp[i - 1][j] (不取)) if(dp[i−1][j−v[i]](取)∣∣dp[i−1][j](不取)) -> d p [ i ] [ j ] = 1 dp[i][j] = 1 dp[i][j]=1

最後一行從後往前看：如果能裝，就用sum減容量(j),再減j，就得出了結果。

優化

既然是01背包，那麼就一定可以做

空間優化

我們可以用滾動數組來做……

(不解釋，直接上代碼)

代碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[105], dp[2][5000005], sum = 0, ans = 0;
int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i]; //算sum的值
    }
    ll V = sum / 2;
    dp[0][0] = 1; //賦初值(至少也得有一種吧)
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= V; j++) {
            if(j < a[i]) dp[i % 2][j] = dp[(i - 1) % 2][j]; //判斷空間是否足夠，若不夠，不放
            else if(dp[(i - 1) % 2][j - a[i]] || dp[(i - 1) % 2][j]) dp[i % 2][j] = 1; //放
            else dp[i % 2][j] = 0; //不放
        }
    }
    for (ll j = V; j >= 0; j--) { //搜尋答案
        if(dp[n % 2][j]) {
            ans = j;
            cout << (sum - ans) - ans << endl; // 得到答案
            return 0;
        }
    }
    return 0;
}
           

(重點來了)坑點講解

這道題坑點多多，是一道名副其實的

坑

題

空間優化前的代碼放上~~

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[105], dp[102][5000002], sum = 0, ans = 0;
int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i]; //算sum的值
    }
    int V = sum / 2;
    dp[0][0] = 1; //賦初值(至少也得有一種吧)
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            if(j < a[i]) dp[i][j] = dp[i - 1][j]; //判斷空間是否足夠，若不夠，不放
            else if(dp[i - 1][j - a[i]] || dp[i - 1][j]) dp[i][j] = 1; //放
        }
    }
    for (int j = V; j >= 0; j--) {
        if(dp[n][j]) {
            ans = j;
            cout << (sum - ans) - ans << endl;
            return 0;
        }
    }
    return 0;
}
           

因為此題要求的數最大可以是 1 0 5 10^5 105，可以有 100 100 100個數，經作者計算後，發現一半就有 5 × 1 0 6 5 \times 10^6 5×106，結果數組開不下了。。。

若dp[0][0]沒有賦初值為1，那麼程式跑出來就全都是0。

記住：j < a[i] 這個判斷 一定 要加！不然的話。。。 ↓ \downarrow ↓(看下圖)

else if 後面的條件是兩個，一個是 取 的結果，一個是 不取 的結果。

最後求答案一定是 反 着來，因為你要的值越大越好。

作者最後發現這道題可以 卡 過去，因為數組可以“卡入膏霜”。。。 ↓ \downarrow ↓(看下圖 + 代碼)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[105], dp[102][2624004], sum = 0, ans = 0; // 注意dp數組，他可是重點（卡出來的）
int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    int V = sum / 2;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            if(j < a[i]) dp[i][j] = dp[i - 1][j];
            else if(dp[i - 1][j - a[i]] || dp[i - 1][j]) dp[i][j] = 1;
        }
    }
    for (int j = V; j >= 0; j--) {
        if(dp[n][j]) {
            ans = j;
            cout << (sum - ans) - ans << endl;
            return 0;
        }
    }
    return 0;
}
           

雖然可以卡過去，但是建議大家最好還是做一下優化，以防空間不足，數組越界的問題。

編譯錯誤顯示：

/tmp/ccI3ZDbs.o: In function `main':
a.cpp:(.text.startup+0x42): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccI3ZDbs.o
a.cpp:(.text.startup+0xbb): relocation truncated to fit: R_X86_64_32S against symbol `a' defined in .bss section in /tmp/ccI3ZDbs.o
collect2: error: ld returned 1 exit status
           

是以，做空間優化還是非常非常

重要

的。。。

最後，思路說清楚了，大家也一定非常明白了吧。

(進入下一節)

多重背包(基礎 -> 優化)

截我回目錄

未完待續

完全背包(基礎 -> 優化)

截我回目錄

未完待續