背包dp学习笔记

By Jeffery

背包种类

1、01背包

名思顾意，只有两种选择：0（不拿）或1（拿）。

2、多重背包

也可以从名字里看出来，有$a[i]$+1种选择,分别是取0,1,2,3 $\cdots$ $a[i]$件物品

3、完全背包

可以取无限件，有无限种选择。

共同点（背包三要素）

都有物品重量、背包容量，物品价值。

示例代码

01背包

未优化

此方法的dp六要素

1.阶段dp[前1~i个物品][容量为1~j];

2.状态（受哪些对象约束）物品重量，背包容量，物品价值

3.决策放或不放

4.状态转移方程dp[i][j]=max(dp[i-1][j]/*不放*/,dp[i-1][j-w[i]]+c[i]/*放*/)

5.初始值i=1,j=m

6.目标值dp[n][1]

代码

for(int i=1;i<=n;++i)//阶段:物品
{
	for(j=m;j>=1;j--)//状态:dp[i][j]
	{
		dp[i][j]=max(dp[i-1][j]/*不放*/,dp[i-1][j-w[i]]+c[i]/*放*/);//状态转移方程
	}
}

优化后

省略了第一维

此方法的dp六要素

1.阶段[容量为1~j];

2.状态（受哪些对象约束）物品重量，背包容量，物品价值

3.决策放或不放

4.状态转移方程dp[j]=max(dp[j]/*不放*/,dp[j-w[i]]+c[i]/*放*/)

5.初始值j=m

6.目标值dp[1]

代码

//dp[容量为j];
for(int i=1;i<=n;++i)//阶段:物品
{
	for(j=m;j>=1;j--)//状态:dp[j]
	{
		dp[j]=max(dp[j]/*不放*/,dp[j-w[i]]+c[i]/*放*/);//状态转移方程
	}
}

多重背包

此方法的dp六要素

1.阶段dp[前1~i个物品][容量为1~j];

2.状态（受哪些对象约束）背包容量，物品重量，物品价值，物品数量

3.决策放1~p[i]个或不放

4.状态转移方程dp[i][j]=max(dp[i][j]/*不放*/,dp[i-1][j-k*w[i]]+k*c[i]/*放*/)

5.初始值i=1,j=1,k=0

6.目标值dp[n][v]

代码

//p[i]:第i种物品的数量
//w[i]:第i种物品的重量
for(int i=1;i<=n;++i)//阶段:物品
{
	for(j=1;j<=v;j--)
	{
		for(int k=0;k<=p[i]&&k*w[j]<=j;k++)
		{
			dp[i][j]=max(dp[i][j]/*不放*/,dp[i-1][j-k*w[i]]+k*c[i]/*放*/);//状态转移方程
		}
	}
}

完全背包

虽然完全背包能取无限件，但最多只能把背包塞满，所以完全背包可以像多重背包来解

此方法的dp六要素

1.阶段dp[前1~i个物品][容量为1~j];

2.状态（受哪些对象约束）物品重量，背包容量，物品价值

3.决策放1~w[i]件或不放

4.状态转移方程dp[i][j]=max(dp[j]/*不放*/,dp[j-w[i]]+c[i]/*放*/)

5.初始值i=1,j=w[i]

6.目标值dp[n][m]

代码

for(int i=1;i<=n;++i)//阶段:物品
{
	for(j=w[i];j<=m;++j)//状态:dp[i][j]
	{
		dp[i][j]=max(dp[j]/*不放*/,dp[j-w[i]]+c[i]/*放*/);//状态转移方程
	}
}