01背包-有解無憂

問題：

　　有 $N$

　　第 $i$

　　求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
　　輸出最大價值，

　　輸入格式

　　第一行兩個整數， $N ， V$

　　接下來有 $N$

　　輸出格式

　　輸出一個整數，表示最大價值，

　　資料范圍

$0 < N, V \leq 1000$

最優方案，就是對兩種選擇的價值取最大值，即f(i, j) = max(f(i-1, j), f(i-1, j-vi) + wi)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1001;

int n,m; // n個物品，總體積不超過m

int p[N][N]; // 總價值

int v[N], w[N]; // 分別為物品的體積和價值

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            p[i][j] = p[i - 1][j];
            if (j >= v[i]) {
                p[i][j] = max(p[i][j], p[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    
    int res = 0;
    for (int i = 0; i <= m; i ++) {
        res = max(res, p[n][i]);
    }
    
    cout << res << endl;
    return 0;
}

優化空間復雜度

從上面來看，主回圈計算出了p[n][m]的結果，但是最后取最佳結果的時候，使用的是p[n][0~m]的最大值，所以我們可以考慮用一維陣列p[0~m]來保存結果，

f(i, j)是有f(i - 1, j)和f(i - 1, j - vi) + wi 遞回而來的，為了保證算出來的f(j)中，使用的f(j - vi)是上一次的計算結果，那么從回圈的角度來看，必須保證j是從大到小回圈的，

例如：第一個物品體積是1，價值是2，背包總容量是5；如果我們先算p[2] = 2，再算p[4] = max(p[4], p[2] + 2)，此時使用的p[2]不再是不選商品時的計算結果，而是已經放入了第一個商品的計算結果，會導致一個商品多次重復放入的問題，

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1001;

int n,m; // n個物品，總體積不超過m

int p[N]; // 總價值

int v[N], w[N]; // 分別為物品的體積和價值

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j --) {
            p[j] = max(p[j], p[j - v[i]] + w[i]);
        }
    }
    
    cout << p[m] << endl;
    return 0;
}

如果要求出是否能正好裝滿背包，那么只需要把p[0]賦值為0，p[1~m]賦值為-1，只有當容量為0時，不裝任何物品背包就是滿的，初始化時其他容量都是不可確認的，

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1001;

int n,m; // n個物品，總體積不超過m

int p[N]; // 總價值

int v[N], w[N]; // 分別為物品的體積和價值

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= m; i++) p[i] = -1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j --) {
            if (p[j - v[i]] != -1)
                p[j] = max(p[j], p[j - v[i]] + w[i]);
        }
    }
    
    if (p[m] != -1) {
        cout << p[m] << endl;
    } else {
        cout << "無法裝滿背包" << endl;
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144589.html

標籤：其他

上一篇：新手咨詢EC2連接問題

下一篇：A. Peter and Snow Blower 決議(思維、幾何)