背包问题温习_alaso_shuang的博客-爱代码爱编程

01背包：选一次，即 用一维优化时，需要倒序，因为选取的是上一行的更新，如果正序操作会覆盖掉最小的体积

完全背包：一个物品可以选多次，即 一维用优化时，正序即可，因为我们物品可以选多次，上一个转移方程可以来自同一行的前面几个值

若用二维，01背包是上一个背包转移过来的所以 i  - 1

完全背包二维的话就是直接 i 

//完全背包(与01背包不同，物品可以放多次)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int f[N][N];
int v[N],w[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 = 1;j <= m;j++)
        {
            if(j < v[i])f[i][j] = f[i-1][j];
            else f[i][j] = max(f[i-1][j],f[i][j-v[i]] + w[i]);
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}
//一维优化
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int f[N];
int v[N],w[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 = 1;j <= m;j++)
        {
            if(j < v[i]) f[j] = f[j];
            else f[j] = max(f[j],f[j-v[i]] + w[i]);
        }
    }

    cout<<f[m]<<endl;
    return 0;
}

//继续优化
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int f[N];
int v[N],w[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;
}

多重背包一

其实就是01背包的变种，不过我们需要用二进制优化

//多重背包(有范围限定)
//可以转化成01背包完成
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int n,m;
int f[N][N],v[N],w[N],ans;
int s[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--)
        {
            for(int k = 0;k <= s[i] && k * v[i] <= j;k++)
            f[j] = max(f[j],f[j - k * v[i]] + k * w[i]);
        }
    }
    
//复杂度太高，不适合写

    return 0;
}

//二进制优化
//(优化为01背包问题)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int n,m,v,w,s;
int vv[N],ww[N];
int f[N];
int main()
{
    cin>>n>>m;
    int num = 1;
    for(int i = 1;i <= n;i++)
    {
    cin>>v>>w>>s;
    for(int j = 1;j <= s;j<<=1)
    {
        vv[num] = j * v;//存体积
        ww[num++] = j * w;//存价值
        s -= j;//减去拆分系数
    }
    if(s)//剩余
    {
        vv[num] = s * v;
        ww[num++] = s * w;
    }
    
    }
    for(int i = 1;i < num;i++)//小于num是因为退出num拆分循环的时候,num++
    {
        for(int j = m;j >= vv[i];j--)
        {
            f[j] = max(f[j],f[j - vv[i]] + ww[i]);
        }
    }
    cout<<f[m]<<endl;




    return 0;
}