yuzh的博客

❤ ECUST ❤

0%

背包问题

发表于 Valine：

确定状态表示：dp[i][j]表示在背包容量为j时，从下标为0到i的物品里任意取的最大价值。

01背包

模板：洛谷P1048

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct item{
	int size, value;
}a[110];

int dp[1010][1010];

int main()
{
	int t,m;
	cin>>t>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].size>>a[i].value;
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=t;j++)
		{
			if(j>=a[i].size) 
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-a[i].size]+a[i].value);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	
	cout<<dp[m][t];
	
	return 0;
}

完全背包

先继承上一层状态->若放得下就与当前行的项进行比较

模板：洛谷P1616

1
2
3
4
5
6
7
8
9
for(int i=1;i<=m;i++)
{
    for(int j=1;j<=t;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=a[i].size) 
            dp[i][j]=max(dp[i][j], dp[i][j-a[i].size]+a[i].value);
    }
}

多重背包

利用二进制将多重背包问题转换为01背包问题即可，时间复杂度会降低至原来的对数级别。