您當前位置：首頁 > php開源 > 綜合技術 > 背包9講，總結

背包9講，總結

來源：程序員人生發布時間：2016-10-06 09:23:35 閱讀次數：2526次

01背包


#include <bits/stdc++.h>
using namespace std;
#define N 107
int dp[N];
int v[N]; // 體積
int w[N]; // 價值
int n, tar;

void ZeroOnePack(int V, int W) {
    for (int v=tar; v>=V; v--)
        dp[v] = max(dp[v-V] + W, dp[v]);
}

int main() {
    freopen("in.txt", "r", stdin);
    cin >> n >> tar;
    for (int i=1; i<=n; i++)  cin >> w[i] >> v[i];
    for (int i=1; i<=n; i++) {
        ZeroOnePack(v[i], w[i]);
    }


    cout << dp[tar] << endl;

}

恰好裝滿背包，那末就是除dp[0]是0以外，其他的都是-INF
如果是不能裝滿背包，那末dp所有的值，都是0

下面相同

完全背包

void CompletePack(int V, int W) {
    for (int v=V; v<=tar; v++) {
        dp[v] = max(dp[v-V]+W, dp[v]);
    }
}

多重背包

解法1：轉化為多重背包

這是1個多重背包的模板，也是10分好用的1種模板，由于這個比直接撤除01 背包來做要省些時間。這是為啥呢，首先先由我講1下為何能換成01 背包吧。

舉個栗子吧。假設給了我們價值為 2，但是數量卻是10 的物品，我們應當把10給拆開，要知道2進制可是能夠表示任何數的，所以10 就是可以有1，2, 4，8以內的數把它組成，1開始我們選上 1了，然后讓10⑴=9，再選上2,9⑵=7，在選上 4,7⑷=3，

而這時候的3<8了，所以我們就是可以得出 10由 1,2,4,3，來組成，就是這個數量為1,2,3,4的物品了，那末他們的價值是甚么呢，是2,4,6,8，也就說給我們的價值為2，數量是10的這批貨物，已轉化成了價值分別是2,4,6,8元的貨物了，每種只有1件哎！！！！這就是2進制優化的思想。

那為何會有完全背包和01 背包的不同使用加判斷呢？緣由也很簡單啊，當數據很大，大于背包的容納量時，我們就是在這個物品中取上幾件就是了，獲得量時不知道的，也就理解為無窮的啦，這就是完全背包啦，反而小于容納量的就是轉化為01背包來處理就是了，可以大量的省時間。

#include<string.h>
#include<stdlib.h>
#define N 1000         //物品個數 
#define M 100000000    //所有物品可能的最大價值 
int m[N],c[N],w[N],f[M];
int V;
int max(int a,int b){return a>b?a:b;}
void ZeroOnePack(int cost,int weight)
{
    int v;
    for(v=V;v>=cost;v--) f[v]=max(f[v],f[v-cost]+weight);
}
void CompletePack(int cost,int weight)
{
    int v;
    for(v=cost;v<=V;v++)
        f[v]=max(f[v],f[v-cost]+weight);
}
void MultiplePack(int cost,int weight,int amount)
{
    int k;
    if(cost*amount>=V) // 實際上這里轉化成了1個無窮數量的完全背包。
    {
        CompletePack(cost,weight);
        return;
    }
    k=1;
    while(k<amount)
    {
        ZeroOnePack(k*cost,k*weight);
        amount=amount-k;
        k=k*2;
    }
    ZeroOnePack(amount*cost,amount*weight);
}
int main()
{
    int n,i;
    scanf("%d %d",&n,&V);
                                                   // 兩種不同的初始化方式，根據情況自行選擇 
    //memset(f,0,sizeof(f[0])*(V+1));              // 只希望價格盡可能大 
    //memset(f,-M,sizeof(f[0])*(V+1));f[0]=0;      // 要求恰好裝滿背包 
    for(i=0;i<n;i++) scanf("%d %d %d",m+i,c+i,w+i);
    for(i=0;i<n;i++) MultiplePack(c[i],w[i],m[i]);
    printf("%d\n",f[V]);
    system("PAUSE");
    return 0;
}

解法2：單調隊列優化

本質是保護1個滑動的窗口，窗口的大小不能超過 m[i]的大小
因而根據w[i]的大小，將原來的j劃分成了w[i]個等價類，每一個等價類，可以進行單調隊列的保護。
將每一個等價類保護1遍以后，就是完成了i個物品的工作
實際上我們可以模仿，01背包問題，進行數組的重復利用

先看1個例子：取m[i] = 2, v[i] = v, w[i] = w, V > 9 * v，
并假定 f(j) = F[i - 1][j]，視察公式右側要求最大值的幾項：

j = 6*v:   f(6*v)、f(5*v)+w、f(4*v)+2*w 這3個中的最大值
j = 5*v:   f(5*v)、f(4*v)+w、f(3*v)+2*w 這3個中的最大值
j = 4*v:   f(4*v)、f(3*v)+w、f(2*v)+2*w 這3個中的最大值
明顯，公式㈠右側求最大值的幾項隨j值改變而改變，但如果將j = 6*v時，每項減去6*w，j=5*v時，每項減去5*w，j=4*v時，每項減去4*w，就得到：
j = 6*v:   f(6*v)-6*w、f(5*v)-5*w、f(4*v)-4*w 這3個中的最大值
j = 5*v:   f(5*v)-5*w、f(4*v)-4*w、f(3*v)-3*w 這3個中的最大值
j = 4*v:   f(4*v)-4*w、f(3*v)-3*w、f(2*v)-2*w 這3個中的最大值

因此隊列中我們是保護1個單調的函數，但是真正使用的時候，我們對這個函數進行適當的處理便可。

#include <iostream>
using namespace std;
#define N 107
int n, tar;
int v[N], w[N], m[N];

int dp[N]; // 轉動數組
int deq[N]; // 單調隊列，下標
int deqv[N]; // 單調隊列，值

void solve() {
    for (int i=0; i<n; i++) { // 枚舉每一個物品
        for (int a=0; a<v[i]; a++) { // 1共v[i]個等價類
            int s =0, t = 0; //雙端隊列的頭部和尾部
            for (int j=0; j*v[i] + a<=tar; j++) { // 每一個等價類中符合條件的j有哪些
                // 加入j構成的函數的時候，保證隊列的單調性
                int val = dp[j * v[i] + a] - j * w[i];
                while (s < t && deqv[t -1] <= val) t--;
                deq[t] = j;
                deqv[t] = val;
                t ++;
                // 從頭部取出，t
                dp[j*v[i] + a] = deqv[s] + j * w[i];

                //判斷隊列的長度是否是太長了
                if (deq[s] == j-m[i]) {
                    s ++;
                }
            }
        }
    }
    cout << dp[tar] << endl;
}

混合背包

for i = 1 to N
    if 第i件物品屬于01背包
        ZeroOnePack(F,Ci,Wi)
    else if 第i件物品屬于完全背包
        CompletePack(F,Ci,Wi)
    else if 第i件物品屬于多重背包
        MultiplePack(F,Ci,Wi,Ni)

2維費用背包

5.1 問題
2維費用的背包問題是指：對每件物品，具有兩種不同的空間耗費，選
擇這件物品必須同時付出這兩種代價。對每種代價都有1個可付出的最大值
（背包容量）。問怎樣選擇物品可以得到最大的價值。
設這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別
為Ci和Di。兩種代價可付出的最大值（兩種背包容量）分別為V 和U。物品的
價值為Wi。
5.2 算法
費用加了1維，只需狀態也加1維便可。設F [i,v,u]表示前i件物品付出兩
種代價分別為v和u時可取得的最大價值。狀態轉移方程就是：
F [i,v,u] = max{F[i ? 1, v, u], F[i ? 1, v ? Ci, u ? Di] + Wi}
如前述優化空間復雜度的方法，可以只使用2維的數組：當每件物品只可
以取1次時變量v和u采取逆序的循環，當物品有如完全背包問題時采取順序的
循環，當物品有如多重背包問題時拆分物品。
這里就不再給出偽代碼了，相信有了前面的基礎，讀者應當能夠自己實現
出這個問題的程序。

注意費用背包的變形

有時，“2維費用”的條件是以這樣1種隱含的方式給出的：最多只能
取U件物品。這事實上相當于每件物品多了1種“件數”的費用，每一個物品的
件數費用均為1，可以付出的最大件數費用為U。換句話說，設F [v,u]表示付
出費用v、最多選u件時可得到的最大價值，則根據物品的類型（01、完全、多
重）用不同的方法循環更新，最后在f[0...V, 0...U]范圍內尋覓答案。

分組背包


有N件物品和1個容量為V 的背包。第i件物品的費用是Ci，價值是Wi。這
些物品被劃分為K組，每組中的物品相互沖突，最多選1件。求解將哪些物品
裝入背包可以使這些物品的費用總和不超過背包容量，且價值總和最大。
算法
這個問題變成了每組物品有若干種策略：是選擇本組的某1件，還是1件
都不選。也就是說設F [k, v]表示前k組物品花費費用v能獲得的最大權值，則
有：
F [k, v] = max{F [k ? 1, v], F [k ? 1, v ? Ci] + Wi | item i ∈ group k}
使用1維數組的偽代碼以下：
for k = 1 to K
for v = V to 0
for item i in group k
F [v] = max{F [v], F [v ? Ci] + Wi}
這里3層循環的順序保證了每組內的物品最多只有1個會被添加到背包中。
另外，明顯可以對每組內的物品利用2.3中的優化。
小結
分組的背包問題將彼此互斥的若干物品稱為1個組，這建立了1個很好的
模型。很多背包問題的變形都可以轉化為分組的背包問題（例如7），由分組的
背包問題進1步可定義“泛化物品”的概念，10分有益于解題。