标签：std 背包 int max 树形 maxn 物品 dp

背包dp

0/1背包

这种背包会提供可选的物品，背包的容积以及每件物品的价值，并且在选择物品是每件物品只有选一件或不选两种状态。
例题

输入
4 5
1 2
2 4
3 4
4 5
输出
8

二维解法代码

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

#include"bits/stdc++.h"
using namespace std;

const int maxn=1010;
const int maxw=1010;

//f[i][j]表示前i件物品占j空间的最大价值
//v[i]表示第i件物品所占的体积
//w[i]表示选第i件物品可以创造的价值
int f[maxn][maxn],v[maxn],w[maxn];
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=0;j<=m;j++)
        //记录背包的容量
		{
			f[i][j]=f[i-1][j];
            //若不选第i件物品，前i件物品创造的价值等于前i-1件物品创造的价值
			if(j>=v[i])
            //保证背包剩余的容量可以装下第i件物品
			{
				f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
                //若选第i件物品，比较不选i和选i所创造的价值，f[i][j]为两种情况中更优的一种
			}
		}
	}
	cout <<f[n][m];
    //输出前n件物品占m容量时的最大价值
	
	return 0;
}

本题中背包现在的状态会存入i中，背包上一次的状态存在于i-1中，而现在的状态只与上一次的状态有关，所以可以用滚动数组将二维优化为一维

一维解法代码

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

#include"bits/stdc++.h"
using namespace std;

const int maxn=1010;
const int maxw=1010;

////f[i][j]仍然表示前i件物品占j空间的最大价值，但i体现在第一层循环中
int f[maxw],v[maxn],w[maxn];
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=m;j>=v[i];j--)
        //背包容量需要倒序保证每个物品只会被判断一次，即保证每种物品最多选一个（必须倒序）
		{
			f[j]=max(f[j],f[j-v[i]]+w[i]);
		}
	}
	cout <<f[m];
	
	return 0;
}

完全背包

在完全背包中，所提供的物品不仅有价值和所占容积，还会提供每种物品拥有的数量，也就是说，每种物品有选一件，选多件和不选三种状态，而选一件和选多件可以统一看成选k件
例题
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
输入
10 4
2 1
3 3
4 5
7 9
输出
max=12

二维解法代码

//状态转移方程与0/1背包很像，只是每种物品选择的数量由一件变为k件
//状态转移方程：f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i][j])

#include"bits/stdc++.h"
using namespace std;

const int maxn=3000;

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

int main()
{
	cin >>m>>n;
	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-k*v[i]]+k*w[i]);
			}
		}
	}
	cout <<"max="<<f[n][m];
	
	return 0;
}

与0/1背包相同，完全背包现在的状态i也只与上个状态i-1相关，所以也可以用滚动数组优化为一维

一维解法代码

//状态转移方程与0/1背包相似
//状态转移方程：f[j]=max(f[j-k*v[i]]+k*w[i],f[j])
//但我们可以将完全背包看成0/1背包，此时需要将每个物品看做一个选取对象，而不是一种物品，此时状态转移方程就变为0/1背包的状态转移方程
//状态转移方程为：f[j]=max(f[j],f[j-v[i]]+w[i])

#include"bits/stdc++.h"
using namespace std;

const int maxn=3000;

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

int main()
{
	cin >>m>>n;
	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++)
        //这层循环是完全背包和0/1背包不同的地方，正序遍历为了把每种物品中的每个拆开，从而使完全背包变为0/1背包（必须正序）
		{
			f[j]=max(f[j],f[j-v[i]]+w[i]);
		}
	}
	cout <<"max="<<f[m];
	
	return 0;
}

多重背包

多重背包与完全背包相似，但多重背包每种物品的个数是有限的（既k∈s[i]）
例题

输入
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出
10

转0/1背包解法代码

//通过遍历的物品的顺序已经将多重背包转化为0/1背包，所以状态转移方程和0/1相同
//状态转移方程：f[j]=max(f[j],f[j-v[i]]+w[i])

#include <bits/stdc++.h>
using namespace std;

const int maxn=110;

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

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<=s[i];j++)//i，j两层循环将每种物品的每一个拆分开，形成0/1背包
		{
			for(int k=m;k>=v[i];k--)
			{
				f[k]=max(f[k],f[k-v[i]]+w[i]);
			}			
		}
	}
	cout <<f[m];

	return 0;
}

直接将多重背包转换为0/1背包的复杂度很大，容易被卡时间，所以可以用二进制拆分进行优化

二进制拆分

原理
任何数字都可以表示成若干个2ⁿ的和(eg:7=2º+2¹+2²)，因为任何整数都可以转成二进制，二进制就是若干个“1”（2的幂数）的和，所以我们可以将物品i拆成体积为v[i]×2ⁿ，价值为w[i]×2ⁿ的若干个物品

二进制拆分解法代码

//已经通过二进制拆分将物品拆成0/1背包，所以状态转移方程与0/1背包相同
//状态转移方程为：f[j]=max(f[j],f[j-v[i]]+w[i])

#include <bits/stdc++.h>
using namespace std;

const int maxn=15000;
const int maxm=2010;

int n,m;	 
int f[maxm];	 
int v[maxn],w[maxn],s[maxn],cnt;	 

int main()
{	
	int vi,wi,si;
	cin >>n>>m;

	//二进制拆分
	for(int i=1; i<=n; i++)
	{
		cin >>vi>>wi>>si;
		if(si>m/vi)si=m/vi;
		for(int j=1;j<=si;j<<=1)
		{
			v[++cnt]=j*vi;
			w[cnt]=j*wi;
			si-=j;
		}
		if(si>0)
		{
			v[++cnt]=si*vi;
			w[cnt]=si*wi;
		}
	}
	
	//0/1背包
	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];

	return 0;
}

分组背包

分组背包中物品和0/1背包相同，都是以个位单位，但是分组背包中的物品会划分到不同的组中，并且题中会出现与组相关的限制条件
例题
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
输入格式
第一行：三个整数，V(背包容量，V<=200)，N(物品数量，N<=30)和T(最大组号，T<=10)；
第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。
输出格式
仅一行，一个数，表示最大总价值。
输入
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
输出
20

二维解法代码

//分组背包就是以组为单位进行0/1背包，所以状态转移方程和0/1背包相同
//状态转移方程：:f[i][j]=max(f[i-1][j],f[i-1][j-v[g[i][k]]]+w[g[i][k]]

#include"bits/stdc++.h"
using namespace std;

const int maxn=2500;

int n,m,t;
int v[maxn],w[maxn];
int dp[15][maxn],g[15][maxn];
//dp[i][j]表示在背包容量为j对第i组的第k个物品的决策最大值
//g[i][j]表示第i组第j个物品的编号

int main()
{
    cin >>m>>n>>t;
    int x;
    for(int i=1;i<=n;i++)
    {
        cin >>v[i]>>w[i]>>x;
        g[x][++g[x][0]]=i;
    }
    //以组为单位进行0/1背包
    for(int i=1;i<=t;i++)
    {
        //0/1背包
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            for(int k=1;k<=g[i][0];k++)
            {
                if(j>=v[g[i][k]])
                {
                    x=g[i][k];
                    dp[i][j]=max(dp[i][j],dp[i-1][j-v[x]]+w[x]);
                }
            }
        }
    }
    cout <<dp[t][m];

    return 0;
}

在分组背包中，当前组i所产生的最大价值只与上一组i-1所产生的最大价值有关，所以可以用滚动数组优化

一维解法代码

//分组背包就是以组为单位进行0/1背包，所以状态转移方程和0/1背包相同
//状态转移方程为：f[j]=max(f[j],f[j-v[i]]+w[i])

#include"bits/stdc++.h"
using namespace std;

const int maxn=2500;

int n,m,t;
int v[maxn],w[maxn];
int dp[maxn],g[15][maxn];

int main()
{
    cin >>m>>n>>t;
    int x;
    for(int i=1;i<=n;i++)
    {
        cin >>v[i]>>w[i]>>x;
        g[x][++g[x][0]]=i;
    }
    //以组为单位进行0/1背包
    for(int i=1;i<=t;i++)
    {
        //0/1背包（与一维0/1背包相同，需要倒序遍历）
        for(int j=m;j>=0;j--)
        {
            for(int k=1;k<=g[i][0];k++)
            {
                if(j>=v[g[i][k]])
                {
                    x=g[i][k];
                    dp[j]=max(dp[j],dp[j-v[x]]+w[x]);
                }
            }
        }
    }
    cout <<dp[m];

    return 0;
}

二维费用背包

顾名思义，这种背包需要开二维的dp（至少目前没见过用一维的），这种背包和其他背包不同的是，它不只有体积这一个限制，还有质量的限制（当然体积和质量用别的也可以平替），所以我们在遍历时需要体找到积不超限制的同时质量也不超限制的最优方案
例题
航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.
输入格式
第一行两个数体积最大值(<400)和质量最大值(<400)
第二行一个数食品总数N(<50).
第三行－第3+N行
每行三个数体积(<400) 质量(<400) 所含卡路里(<500)
输出格式
一个数所能达到的最大卡路里(int范围内)
输入
320 350
4
160 40 120
80 110 240
220 70 310
40 400 22
输出
550

唯一会的一种解法代码

//因为有两个条件限制，所以状态转移方程中应出现两个条件
//状态转移方程：f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i])(i为物品的编号)

#include"bits/stdc++.h"
using namespace std;

const int maxn=10000;

//f[i][j]表示在体积不超过i且质量不超过j时的最优方案
int f[maxn][maxn],v[maxn],m[maxn],w[maxn];
int n,maxt,maxm;

int main()
{
	cin >>maxt>>maxm>>n;
	for(int i=1;i<=n;i++)
	{
		cin >>v[i]>>m[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=maxt;j>=v[i];j--)
		{
			for(int k=maxm;k>=m[i];k--)
			{
				f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
			}
		}
	}
	cout <<f[maxt][maxm];
	
	return 0;
}

标签：std,背包,int,max,树形,maxn,物品,dp
From： https://www.cnblogs.com/wang-qa/p/18017815

dp总结（背包，线性，区间，坐标，树形）

背包dp

0/1背包

完全背包

多重背包

二进制拆分

分组背包

二维费用背包

相关文章

赞助商

阅读排行