背包問題幾種情況的初始化(至少、至多、恰好、求數量)

題目會逐漸更新在後面，前面隻是結論；

簡單介紹

至多是我們最常見的情況，通常描述為，不超過xxx；

而恰好以及至少是比較不常見的；

二維情況

1、體積至多 j ， f [ i , k ] = 0 ， 0 < = i < = n , 0 < = k < = m j，f[i,k] = 0，0 <= i <= n, 0 <= k <= m j，f[i,k]=0，0<=i<=n,0<=k<=m（一般隻會求價值的最大值）

2、體積恰好 j j j，

當求價值的最小值： f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0, 其餘是 I N F INF INF

當求價值的最大值： f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0, 其餘是 − I N F -INF −INF

之是以這裡 f [ i ] [ 0 ] , i > 0 ， f[i][0],i>0， f[i][0],i>0，不初始化為0，要看題目的，如果題目允許了0體積的物品且有價值，那就非法了；

而且，一般我們都是按順序枚舉物品的，狀态會逐漸轉移上去的，是以我認為沒必要給f[i][0]設定合法狀态，後面同理；

3、體積至少是 j j j， f [ 0 ] [ 0 ] = 0 f[0][0] = 0 f[0][0]=0，其餘是 I N F INF INF（一般隻會求價值的最小值）

一維情況

1、體積至多 j ， f [ i ] = 0 , 0 < = i < = m j，f[i] = 0, 0 <= i <= m j，f[i]=0,0<=i<=m（隻會求價值的最大值）

2、體積恰好 j j j，

當求價值的最小值： f [ 0 ] = 0 f[0] = 0 f[0]=0, 其餘是 I N F INF INF

當求價值的最大值： f [ 0 ] = 0 f[0] = 0 f[0]=0, 其餘是 − I N F -INF −INF

3、體積至少 j j j， f [ 0 ] = 0 f[0] = 0 f[0]=0，其餘是 I N F INF INF（一般隻會求價值的最小值）

稍微解釋一下這些初始化；

至多的情況

也就是不超過xxx；

那麼0也是不超過xxx(xxx>=0)，是以初始值可以全部給0，也就是都是合法的；

恰好的情況

恰好為多少，那麼隻有 f [ 0 ] [ 0 ] = 0 f[0][0]=0 f[0][0]=0是合法的，其他都是非法狀态，是以根據題意給 I N F INF INF或者 − I N F -INF −INF

至少的情況

因為你現在是初始狀态，你不可能有比0大的合法狀态，是以除了至少為0都是非法的；

故 f [ 0 ] [ 0 ] = 0 f[0][0]=0 f[0][0]=0，其他情況給非法狀态；

求方案數

要看題意;

如果題意描述的是恰好

因為什麼都不選，也是一種方案，是以方案數為1

二維 f [ 0 ] [ 0 ] = 1 f[0][0]=1 f[0][0]=1

一維 f [ 0 ] = 1 f[0]=1 f[0]=1

如果題意描述的是不超過

二維 f [ 0 ] [ j ] = 1 f[0][j] = 1 f[0][j]=1

一維 f [ j ] = 1 f[j]=1 f[j]=1

如果題意描述的是至少

二維 f [ 0 ] [ 0 ] = 1 f[0][0] = 1 f[0][0]=1

一維 f [ 0 ] = 1 f[0]=1 f[0]=1

具體題目

潛水員

題目來源

這道題就是至少的情況；

因為題目想要達到要求，且代價最少；

代碼中有一個注意點，這裡解釋一下

注意這裡i和j是要取到0的；

因為我們的初始狀态不一定從0開始；

負數也是合法的；

舉個例子，假設我們體積現在是5；

那麼至少是-2也包含了體積是5；

同理，體積是10也被至少是-2包含；

是以 j − w < 0 j-w<0 j−w<0時的狀态也是合法的；

因為在這題裡；

負數和0是等價的，是以我們用0來代替負數即可；

#include <iostream>
#include <cstring>
using namespace std;

const int N = 60,M = 170;

int f[N][M];

int main(){
    memset(f,0x3f,sizeof(f));
    int ans = f[0][0];
    int n,m,k;
    cin >> n >> m >> k;
    f[0][0]=0;
    while(k--){
        int w1,w2,val;
        cin >> w1 >> w2 >> val;
        //這裡是注意點
        for(int i=n;i>=0;--i){
            for(int j=m;j>=0;--j){
                f[i][j]=min(f[i][j],f[max(0,i-w1)][max(0,j-w2)]+val);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}
           

數字組合

這題是0-1背包求方案數，具體看代碼；

數字組合

#include <iostream>

using namespace std;

const int N = 1e3+10;

int f[N];

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<=m;++i) f[i] = 0;
    f[0] = 1;
    for(int i=1,w;i<=n;++i){
        cin >> w;
        for(int j=m;j>=w;--j){
            f[j]+=f[j-w];
        }
    }
    cout << f[m] << '\n';
    return 0;
}
           

買書

這題是多重背包求方案數

買書

#include <iostream>

using namespace std;

const int N = 1e3+10;

int f[N],a[5];

int main(){
    int m,n=4;
    cin >> m;
    f[0]=1;
    a[1]=10,a[2]=20,a[3]=50,a[4]=100;
    for(int i=1;i<=n;++i){
        for(int j=a[i];j<=m;++j){
            f[j]+=f[j-a[i]];
        }
    }
    cout << f[m] << '\n';
    return 0;
}