背包问题

01背包

每件物品最多只用一次

01背包

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

（1）状态f[j]定义：NN 件物品，背包容量j下的最优解。

（2）注意枚举背包容量j必须从m开始。

（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

（4）例如，一维状态第i轮对体积为 33 的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该是f[i - 1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1][4]。

（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。

作者：深蓝
链接：https://www.acwing.com/solution/content/1374/

//无优化，二维

#include
#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];		//体积和价值
int f[N][N];		//状态

int main(){
    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 = 1;j <= m;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][m];
}


//优化，一维

#include
#include

using namespace std;

const int N = 1010;

int v[N],w[N];
int n,m;
int f[N];

int main(){
    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 --)
            f[j] = max(f[j],f[j - v[i]] + w[i]);		//从大到小迭代

    cout << f[m];
}

完全背包

每件物品有无限个

完全背包

二维向一维转化的时候因为用到的是第 i 层更新所以不用逆序避免 i - 1 被 "污染"

//朴素做法
#include
#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N];

int main(){
    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 ++)
            for(int k = 0;k * v[i] <= j;k ++)
                f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m];
}

//优化一重循环
#include
#include

using namespace std;

const int N = 1010;

int n,m;
int f[N][N];
int v[N],w[N];

int main(){
    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 = 1;j <= m;j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j - v[i]] + w[i]);		//和01背包区别是从i层更新
    	  //if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); //01背包的更新
        }

    cout << f[n][m];
}

//优化至一维
#include
#include

using namespace std;

const int N = 1010;

int n,m;
int f[N];
int v[N],w[N];

int main(){
    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 = v[i];j <= m;j ++)
            f[j] = max(f[j],f[j - v[i]] + w[i]);	//从第i层更新

    cout << f[m];
}

多重背包

每件物品个数给出

多重背包

//朴素写法
#include
#include

using namespace std;

const int N = 110;

int v[N],w[N],s[N];
int n,m;
int f[N][N];

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

    for(int i = 1;i <= n;i ++) cin >> v[i] >> w[i] >> s[i];

    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            for(int k = 0;k <= s[i] && k * v[i] <= j;k ++)	//与完全背包不同之处
                f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + w[i] * k);
    
    cout << f[n][m];
}

//二进制优化
#include
#include

using namespace std;

const int N = 25000;

int f[N];
int v[N],w[N];
int n,m;
int cnt = 0;

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

    for(int i = 0;i < n;i ++){
        int a,b,c;
        cin >> a >> b >> c;

//二进制拆分，可以将k个数组合成c，优化时间复杂度为log c
        int k = 1;
        while(k <= c){
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            c -= k;
            k *= 2;
        }

        if(c > 0){
            cnt ++;
            v[cnt] = a * c;
            w[cnt] = b * c;
        }
    }

    for(int i = 1;i <= cnt;i ++)
        for(int j = m;j >= v[i];j --)
            f[j] = max(f[j],f[j - v[i]] + w[i]);

    cout << f[m];
}

分组背包

每一组最多选一个物品

分组背包

//朴素写法
#include
#include

using namespace std;

const int N = 110;

int n,m;
int f[N][N];
int v[N][N],w[N][N],s[N];

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

    for(int i = 1;i <= n;i ++){
        cin >> s[i];

        for(int j = 1;j <= s[i];j ++)
            cin >> v[i][j] >> w[i][j];
    }

    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++){
            f[i][j] = f[i - 1][j];
            for(int k = 1;k <= s[i];k ++)
                if(j >= v[i][k]) f[i][j] = max(f[i][j],f[i - 1][j - v[i][k]] + w[i][k]);
        }

    cout << f[n][m];
}

//一维优化
#include
#include

using namespace std;

const int N = 110;

int n,m;
int v[N][N],w[N][N],s[N];
int f[N];

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

    for(int i = 1;i <= n;i ++){
        cin >> s[i];

        for(int j = 1;j <= s[i];j ++)
            cin >> v[i][j] >> w[i][j];
    }

    //更新用到的数据是第i - 1层，所以要j从大到小遍历
    for(int i = 1;i <= n;i ++)
        for(int j = m;j >= 0;j --)
            for(int k = 1;k <= s[i];k ++)
                if(v[i][k] <= j)
                    f[j] = max(f[j],f[j - v[i][k]] + w[i][k]);

    cout << f[m];
}