?01背包問題：

給定一個有一定容量的背包，和n個物品，每個物品只能選擇一次。

成都創(chuàng)新互聯(lián)擁有10多年成都網(wǎng)站建設(shè)工作經(jīng)驗,為各大企業(yè)提供成都網(wǎng)站建設(shè)、成都網(wǎng)站制作服務(wù)，對于網(wǎng)頁設(shè)計、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、手機APP定制開發(fā)、wap網(wǎng)站建設(shè)（手機版網(wǎng)站建設(shè)）、程序開發(fā)、網(wǎng)站優(yōu)化（SEO優(yōu)化）、微網(wǎng)站、域名注冊等，憑借多年來在互聯(lián)網(wǎng)的打拼，我們在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了很多網(wǎng)站制作、網(wǎng)站設(shè)計、網(wǎng)絡(luò)營銷經(jīng)驗，集策劃、開發(fā)、設(shè)計、營銷、管理等網(wǎng)站化運作于一體，具備承接各種規(guī)模類型的網(wǎng)站建設(shè)項目的能力。

每個物品有其對應(yīng)的體積和價值。

問背包最多能裝下的物品的大價值為多少。

輸入格式：

第一行兩個整數(shù)，N，V，分別表示物品數(shù)量和背包容積。

接下來有?N?行，每行兩個整數(shù)?vi,wi 用空格隔開，分別表示第?i?件物品的體積和價值。

輸出格式：

輸出一個整數(shù)，表示大價值。

思路：

假設(shè)f[i][j]代表當(dāng)只選擇前n個物品并且背包容量只有j的時候所能裝下物品的大價值

f[i][j] = max(f[i - 1][j]，f[i - 1][j - v[j]] + w[j])

題目的答案就是f[n][m]。

為什么這樣做是正確的呢：

當(dāng)我們在面對第i件物品的時候，我們一定會在選擇第i件物品和不選擇第i件物品這兩種情況中做出選擇。

集合的角度：

假設(shè)我們有一個集合，集合表示的是只看前i件物品，背包容量為j的時候的所有物品選法，f[i][j]取集合中的大值，該集合可以劃分為選擇第i件物品和不選擇第i件物品兩個集合，f[i][j]取兩個集合中的大值即可。

選和不選兩種情況下狀態(tài)的改變：

如果我們不選擇第i件物品，那么我們的背包的價值就不變，等于f[i-1][j]。

如果我們背包的容量足夠，我們選擇第i件物品的話，雖然我們得到了第i件物品的價值，但是我們背包的體積一定會損耗，體積如果損耗，那么我們就有可能放下前面已經(jīng)裝進背包中的物品，此時我們的背包價值是不一定增大的。

所以我們的f[i][j]取兩者的大值，也就是

f[i][j] = max(f[i - 1][j]，f[i - 1][j - v[j]] + w[j])

給出圖示：

代碼如下：

#includeusing namespace std;
const int N = 1010;
int v[N], w[N];//每個物品的體積和價值
int f[N][N];//每個狀態(tài)的大價值
int n, V;//物品數(shù)和背包容量
int main() {
    cin >>n >>V;
    for (int i = 1; i<= n; i++)
        cin >>v[i] >>w[i];

    for (int i = 1; i<= n; i++)
        for (int j = 0; j<= V; 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]] + w[i]);
        }

    cout<< f[n][V];
    return 0;
}

優(yōu)化至一維：

我們發(fā)現(xiàn)，我們在更新的時候只會用到兩層狀態(tài)，每一個狀態(tài)都是由上一層左邊的狀態(tài)推導(dǎo)而來的，我們不妨將這兩行合并。

dp方程為：

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

一維狀態(tài)中，f[j]默認(rèn)就是上一層的f[j]，所以不用進行不選第i個物品的更新。當(dāng)我們選擇第i個物品時當(dāng)，我們需要用到上一層左邊的狀態(tài)，所以我們不能把本層左邊的狀態(tài)更新成上一層左邊的狀態(tài)。如果我們從前往后進行更新，那么上一層的左邊的狀態(tài)就被更新掉了。所以我們應(yīng)該從后往前更新。

代碼如下：

#includeusing namespace std;
const int N = 1010;
int n, V;//物品數(shù)
int v, w;//總體積
int f[N];//狀態(tài)
int main() {
    cin >>n >>V;
    for (int i = 0; i< n; i++) {
        cin >>v >>w;
        for (int j = V; j >= v; j--)
            if (v<= j)f[j] = max(f[j - v] + w, f[j]);//f[j]默認(rèn)就是上一行的值,所以不用更新v小于j的情況
    }

    cout<< f[V];
    return 0;
}

注意：

1.背包問題中的狀態(tài)，無論是一維還是二維，dp數(shù)組要同時滿足背包體積和物品數(shù)量兩個邊界，而不是滿足數(shù)量邊界即可。

2.狀態(tài)更新要用到f[i-1]，所以物品下標(biāo)要從1開始。

例題： 裝箱問題：

有一個箱子容量為 V，同時有 n 個物品，每個物品有一個體積（正整數(shù)）。

在 n 個物品中，任選若干個裝入箱內(nèi)，使箱子的剩余空間為最小。

輸入格式：

第一行是一個整數(shù) V，表示箱子容量(0≤V小于等于20000)。

第二行是一個整數(shù) n，表示物品數(shù)(0≤n≤30)。

接下來 n 行，每行一個正整數(shù)（不超過10000），分別表示這 n 個物品的各自體積。

思路：

題目要盡可能的裝滿箱子。我們給每個物品賦予一個價屬性，價值的值就是體積的值。所以就是求一定體積下的大價值是多少。

代碼如下：

//二維
#includeusing namespace std;

const int N = 20010, M = 40;
int f[M][N];
int n, m;//物品數(shù)和背包容量

int main() {
    cin >>m >>n;

    int v, w;
    for (int i = 1; i<= n; i++) {//前i個物品
        //讀入體積和價值
        cin >>v;
        w = v;
        for (int j = 0; j<= m; j++) {//體積為j
            f[i][j] = f[i - 1][j];//不選該物品
            if (j >= v)f[i][j] = max(f[i][j], f[i - 1][j - v] + w);
        }
    }

    cout<< m - f[n][m];//記得做減法

    return 0;

}

//一維
#includeusing namespace std;

const int N = 20010;
int f[N];
int n, m;//物品數(shù)和背包容量

int main() {
    cin >>m >>n;

    int v, w;
    for (int i = 1; i<= n; i++) {//前i個物品
        //讀入體積和價值
        cin >>v;
        w = v;
        for (int j = m; j >= v; j--) {//從后往前更新
            f[j] = max(f[j], f[j - v] + w);
        }
    }

    cout<< m - f[m];//記得做減法

    return 0;

}

注意:最后輸出的是剩余多少空間，我們求出來的是大體積，所以不要忘記做減法。

數(shù)字組合：

給定?N?個正整數(shù)，從中選出若干個數(shù)，使它們的和為?M，求有多少種選擇方案。

輸入格式

第一行包含兩個整數(shù)?N?和?M（1≤N≤100，1≤M≤10000）。

第二行包含?N?個整數(shù)，表示?A1,A2,…,AN。

輸出格式：

包含一個整數(shù)，表示可選方案數(shù)。

思路：

f[i][j]表示只看前i個物品，和為j的情況。

如果選擇第i個物品：f[i][j] = f[i-1][j-v[i]]。

如果不選第i個物品：f[i][j] = f[i-1][j]。

f[i][j]等于兩者之和。

該題需要初始化，f[0][0] = 1。

代碼如下：

//二維
#includeusing namespace std;

const int N = 110, M = 10010;
int f[N][M];
int n, m;//n個數(shù)和為m

int main() {
    cin >>n >>m;

    int v;

    f[0][0] = 1;

    for (int i = 1; i<= n; i++) {//前i個數(shù)
        cin >>v;
        for (int j = 0; j<= m; j++) {
            f[i][j] += f[i - 1][j];//不選
            if (j >= v)f[i][j] += f[i - 1][j - v];//選
        }
    }

    cout<< f[n][m];

    return 0;
}

//一維
#includeusing namespace std;

const int M = 10010;
int f[M];
int n, m;//n個數(shù)和為m

int main() {
    cin >>n >>m;

    int v;

    f[0] = 1;//初始化

    for (int i = 1; i<= n; i++) {//前i個數(shù)
        cin >>v;
        for (int j = m; j >= v; j--)
            f[j] += f[j - v];//選
    }

    cout<< f[m];

    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：動態(tài)規(guī)劃——01背包問題-創(chuàng)新互聯(lián)
地址分享：http://weahome.cn/article/ipjoi.html