喔是宝藏UP🐖

AcWing 2. 01背包问题(基础)

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

二维01[AC]

#include
using namespace std;
const int N=1010;
int w[N],v[N],f[N][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++)
        {
            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]<<endl;
}

优化思路:二维–>一维

一维01[AC]

#include
using namespace std;

const int N=1010;
int n,m;
int v[N],w[N],f[N];
//f[i]:N 件物品，背包容量j下的最优解。
//删除第一维
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
    {
        //m-->v[i]先计算大的，即f[i][j-v[i]]
        //v[i]-->m先计算小的，即f[i-1][j-v[i]]
        for(int j=m;j>=v[i];j--)
        {
            //f[i][j]=f[i-1][j];
            //f[j]=f[j]
            
            //if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            //f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            
            //v[i]-->m
            //如果删除第一维：f[j]=max(f[j],f[j-v[i]]+w[i])
            //等价于f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
            
            //m-->v[i]
            //如果删除第一维：f[j]=max(f[j],f[j-v[i]]+w[i])
            //等价于f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            
            //原因：
            //eg:v[i]-->m先计算小的，i=1时，由于j-v[1]<j，所以f[j-v[1]]先计算，即f[j-v[1]]是f[1][j-v[i]]
            //在计算f[j]=max(f[j],f[j-v[i]]+w[i])时,用到的是f[1][j-v[1]]+w[i]
            //eg:m-->v[i]先计算大的，i=1时，由于j-v[1]<j，所以f[j]先计算，即f[j-v[1]]是f[0][j-v[i]]
            //在计算f[j]=max(f[j],f[j-v[i]]+w[i])时,用到的是f[0][j-v[i]]+w[i]
            
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }   
        
    }
    
    cout<<f[m]<<endl;
}

AcWing 3. 完全背包问题(基础)

有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i种物品的体积和价值。
输出格式

输出一个整数，表示最大价值。
数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

//01:f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
//完全：f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);

//01：f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);-->用到的是f[i-1][....]故从大到小循环即可
//完全：f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);-->用到的是f[i][....]故从小到大循环即可

//为什么可以2个for:
//因为            
// for(int j=1;j<=m;j++)
// {
//     for(int k=0;k*v[i]<=j;k++)
//     {
//         f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
//     }
// }
//可以转换

三维[TLE]

#include
using namespace std;
const int N=1010;
int w[N],v[N],f[N][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++)
        {
            for(int k=0;k*v[i]<=j;k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
            
        }
    }
    
    cout<<f[n][m]<<endl;
}

优化思路:三for–>二for

二维/一维[AC]【优化：与01背包相同】

#include
using namespace std;
const int N=1010;
int w[N],v[N],f[N][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++)
        {
            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]);
        }
    }
    
    cout<<f[n][m]<<endl;
}

#include
using namespace std;
const int N=1010;
int w[N],v[N],f[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]);
            //f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);-->用到的是f[i][....]故从小到大循环即可
            //f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);-->用到的是f[i-1][....]故从大到小循环即可
        }
    }
    cout<<f[m]<<endl;
}

AcWing 4. 多重背包问题(基础)

有 N 种物品和一个容量是 V的背包。

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。
输出格式

输出一个整数，表示最大价值。
数据范围

0<N,V≤100

0<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

//为什么必须三个for:
//因为            //
//for(int k=0;k=k*v[i])
//    f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
//}
//无法转换

三维[AC]–不能像完全背包的二维优化【原因】

#include
using namespace std;

const int N=110;
int n,m;
int v[N],w[N],s[N];
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++)
            {
                if(j>=k*v[i])
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    
    cout<<f[n][m]<<endl;
}

AcWing 5. 多重背包问题 II (基础)

有 N 种物品和一个容量是 V的背包。

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。
输出格式

输出一个整数，表示最大价值。
数据范围

0<N≤1000

0<V≤2000
0<vi,wi,si≤2000

提示：

本题考查多重背包的二进制优化方法。
输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

优化思路:三维–>01背包问题【二维/一维】

二维[AC]–数据范围变大–二进制优化

//做法：将10分成1,2,4,3
//        16    1,2,4,8,1
//将1，2，4，3，1，2，4，8，1分别变成一个新的物品，然后进行01背包
//原因：复杂度小，而且可以进行组合，变成需要的数量

#include
using namespace std;
const int N=1000*15;//1000*log 2000
int a,b,c,cnt;
int n,m;
int f[N];
int v[N],w[N],s[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b>>c;
        int k=1;//代表捆绑之后的物品个数；
        while(c>=k)
        {
            cnt++;//cnt=[1,n]
            v[cnt]=k*a;
            w[cnt]=k*b;
            c=c-k;
            k=2*k;
        }
        if(c>0)
        {
            
            cnt++;//cnt=1
            v[cnt]=c*a;
            w[cnt]=c*b;
        }
    }
    
    
    int n1=cnt;//捆绑之后的商品数量
    for(int i=1;i<=n1;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    
    cout<<f[m]<<endl;
}

AcWing 9. 分组背包问题(基础)

有 N 组物品和一个容量是 V的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。
输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N组数据：
每组数据第一行有一个整数 Si，表示第 i个物品组的物品数量；每组数据接下来有 Si行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

8

二维/一维[AC]【优化：与01背包相同】

//为什么必须三个for:
//因为必须要用到k
#include
using namespace std;
const int N=110;
int n,m;
int s[N],v[N][N],w[N][N],f[N][N],dp[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];//0
            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]);//1.....s[i]
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

//为什么必须三个for:
//因为必须要用到k
#include
using namespace std;
const int N=110;
int n,m;
int s[N],v[N][N],w[N][N],f[N][N],dp[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=m;j>=0;j--)
            for(int k=0;k<=s[i];k++)
            if(j>=v[i][k])dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
    
    cout<<dp[m]<<endl;
    return 0;
}

AcWing 423. 采药(01背包模板)

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？
输入格式

输入文件的第一行有两个整数 T和 M，用一个空格隔开，T 代表总共能够用来采药的时间