背包问题几种情况的初始化(至少、至多、恰好、求数量)

题目会逐步更新在后面，前面只是结论；

简单介绍

至多是我们最常见的情况，通常描述为，不超过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;
}