完全背包算法笔记

每种物品数量无限的背包问题。

题目描述

\(n\)种物品,和一个容量为\(C\)的背包,每种物品都有无限件可用,第\(i\)件物品的重量是\(w[i]\),价值是\(v[i]\),求这个背包能装的所有物品的总价值最大是多少。

问题分析

类似于01背包问题,只不过是每种物品都有无限件可选,从每种物品的角度考虑,与它相关的策略是取0件,取1件...取很多件。

递推公式: \[ dp[i][j] = max\{dp[i-1][j - k * w[i]] + k * v[i],dp[i-1][j]\}\ \ \ (0 <= k * w[i]<= j) \] 也可以用一维\(dp\)数组来求解。这里就只分析用一维数组的情况。

其实和01背包差不多,但是在遍历\(j\)的时候和初始化不一样。\(dp[j]\)还是表示前\(i\)件物品放入一个为\(j\)容量的背包获得的最大价值,每次更新必然保证是当前最优解。具体分析看例子。

例子:

有5个物品,(重量,价值)分别为:(5,1),(4,2),(3,3),(4,2),(5,1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;

int main()
{
int w[6] = { 0,5,4,3,2,1 };
int v[6] = { 0,1,2,3,4,5 };
int n = 5; //有5个物品
int C = 15; //假定背包的最大容量为15
vector<int> dp(C + 1);
for (int i = 1; i <= n; i++)
{
for (int j = w[i]; j <= C; j++)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[C] << endl;
system("pause");
return 0;
}

首先当只有1号物品的时候,\(j\)初始化为1号物品的重量5。

d[5]=max(dp[5],dp[5-5]+1)=1. dp[6]=1,dp[7...9]=1 dp[10...14]=2,dp[15]=3

在有1,2号物品的时候,\(j\)初始化为2号物品的重量4

dp[4]=max(dp[4],d[4-4]+2)=2 dp[5]=max(dp[5],dp[5-4]+3)=2 dp[8]=max(dp[8],dp[8-4]+2)=4

我们要决定是不是要放这个物品,就从这个物品的大小出发遍历背包容量,然后每次遍历都对比下假如现在腾出这个物品的空间并且放进去比原来的价值还大的话,就放进去。

和01背包的区别:

01背包遍历是反向的,这样更新就不会影响前面的。

而完全背包正向遍历,会改变前面的。继而实现多次拿取。