[数据结构与算法]动态规划_01背包_完全背包_多重背包_分组背包

动态规划问题结题思路：

模板题链接：

01背包模板题
完全背包模板题
多重背包模板题
分组背包

01背包

思路：

定义状态表示函数$f(i,j)：$

j空间大小的背包，在对（1 ~ i）号物品做出选择后，背包能装下的最大价值。

所以产生了如下集合。

在选择i号物品的情况下 : $f(i,j)$的值就为$f(i?1,j?v[i])+w[i]$
在不选择i号物品的情况下 : $f(i,j)$的值就为$f(i?1,j)$
最终的最优解就为$f(物品数量,背包容量)$

代码：

#include<iostream>

using namespace std;

const int N = 1e3+5;

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

int main(){
    int n,m;
    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++){
       		//将这轮for循环转换为从后往前，就可以将二维数组f转换为一维数组f。
            f[i][j]=f[i-1][j];//不放i号物品
            //可以放i号物品的情况下的最大值
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

完全背包

思路:

思路同01背包，完全背包和01背包不同的一点是，01背包每个物品只能取一次，而完全背包一个物品可以取多次。所以$f(i,j)$需要更改表示方式为：
在选择k个i号物品的情况下 :
$f(i,j)=Max(f(i?1,j)，f(i?1,j?v[i])+w[i]，f(i?1,j?2v[i])+2w[i]，...，f(i?1,j?kv[i])+kw[i])$
同时可以观察发现：
$f(i,j?v[i])=Max(f(i?1,j?v[i])，f(i?1,j?2v[i])+2w[i]，f(i?1,j?3v[i])+3w[i]，...，f(i?1,j?kv[i])+kw[i])$
将上面两式合并，得;
$f(i,j)=Max(f(i?1,j)，f(i,j?v[i])+w[i])$
上式和01背包的区别只在后一项上，01背包是只和i-1的状态有关，而完全背包不但和i-1的状态有关，也与i的状态有关。

代码

#include<iostream>

using namespace std;

const int N = 1e3+5;

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

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]); 
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

多重背包

思路：

如果强行按照完全背包思想进行枚举，在有1000个物品以上时，往往会浪费大量时间。这时候，就需要一个操作，将O(n)的复杂度降低到O(logN)。这时就用到了多重背包的二进制转换思想。
假设有一个物品可以取S次，则S一定满足
$S=111...1+C$
其中一共有$?lo{g}_2(S)?$个1，C为一个常数。所以对于任意一个小于S的数s’,都可以通过在 { 2 0 , 2 1 , . . . 2 k } \{2^0,2^1,...2^k\} {20,21,...2k}中取任意一个数和C的组合实现。
于是，一个可以取S次的物品就被拆分成了$?lo{g}_2(S)?+1$个物品。（+1是为了考虑C）
对所有物品经过这些操作以后，就完了问题的转换。将问题转换为了一个标准的01背包问题。

代码：

#include<iostream>

using namespace std;

const int N = 1005,M = 2005;

int v[12005],w[12005],f[2005];
int n,m,cnt;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        //转换物品
        int a,b,s;//体积，权重，最大数量
        cin>>a>>b>>s;
        int k=1;
        while(k<=s){
            cnt++;
            w[cnt]=k*b;
            v[cnt]=k*a;
            s-=k;
            k<<=1;
        }
        if(s)
        {
            cnt++;
            w[cnt]=s*b;
            v[cnt]=s*a;
        }
    }
    //01背包的解法
    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]<<endl;
    return 0;
}

组合背包

思路：

同完全背包问题，只是将一个数去很多次，转换为了多个数取一次。

代码：

#include<iostream>

using namespace std;

const int N=105;

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

int main(){
    int n,m;
    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=m;j>0;j--){//背包大小
            for(int k=1;k<=s[i];k++){//枚举i组的物品
                if(v[i][k]<=j){
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
                }
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}