完全背包问题的解决方法______闫氏 DP 分析法

完全背包问题的解决方法：

闫氏 $DP$ 分析法:
通过集合划分，我们可以得到第 $i$ 个物品有两种状态：
 1.选 $1-T$ 个，最优解为前 $i-1$ 个物品的所有选择中，还能选取当前 $k$ 个第$i$ 个物品的最大价值加上 $k$ 个第 $i$ 个物品本身的价值，即
$dp[i][j]=max(dp[i][j],dp[i-1][j-k\ast v[i]]+k\ast w[i]),(1\le k\le T)$
 2.不选，最优解为前$i-1$个物品的所有选择中的最大价值，即 $dp[i][j]=dp[i-1][j]$
若使用枚举的方式来选取$1-k$个物品 i的情况，会超时，故需分析当前的状态转移方程能否被优化。
我们令该朴素转移方程为 A式：
$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2v]+2w,\cdots ,dp[i-1][j-kv]+kw)$
将左式的$j$替换成$j-v$后，得到 B式：
$dp[i][j-v]=max(dp[i-1][j-v],dp[i-1][j-2v]+w,\cdots ,dp[i-1][j-kv]+(k-1)w)$
仔细观察可以发现，A式从第二项开始与 B 式很相似，两者之间的差异仅为一个 w。
因此，将 A式右边第二项开始替换成 B 式加上一个 w 后，可得 C式：
$dp[i][j]=max(dp[i-1][j],dp[i][j-v]+w)$

3. 完全背包问题

#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];//表示从前i个物品中选,总体积不超过j的方案的集合

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
	
	//完全背包模板
	//遍历物品数，当前是第i件物品
    for (int i = 1; i <= n; i ++ )//物品从第1件开始
    {
    	//遍历背包容量（从小到大遍历，只要空间够，第i件物品想拿几个，就拿几个）
        for (int j = 0; j <= m; j ++ )//空间从0开始
        {
            f[i][j] = f[i-1][j];
            if( j >= v [i] )
            {
                f[i][j] = max(f[i-1][j], f[i][j - v[i]] + w[i]);//公式推导出来的
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}
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
31
32
33
34

改成一维,如下:

#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];//不超过总体积j的方案的集合

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

	//完全背包模板
	//遍历物品数，当前是第i件物品
    for (int i = 1; i <= n; i ++ ){
    	//遍历背包容量（从小到大遍历，只要空间够，第i件物品想拿几个，就拿几个）
        for (int j = v[i]; j <= m; j ++ ){
        		//f[j] = f[j];  等式右边的f[j]表示 : 未更新前的,前i个物品中选,总体积不超过j的方案的集合 ; 等式左边表示更新后的 前i个物品中选,总体积不超过j的方案的集合。所以，与f[i][j] = f[i-1][j];等效
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //cout<
        }
        //cout<
    }            
    cout << f[m] << endl;
    return 0;
}
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

完全背包与01背包的对比

//完全背包模板
	//遍历物品数，当前遍历到的是第i件物品
    for (int i = 1; i <= n; i ++ ){
    	//遍历背包容量（背包能装下的体积）（从小到大遍历）
        for (int j = v[i]; j <= m; j ++ ){//[v[i],m]
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }            
    cout << f[m] << endl;
1
2
3
4
5
6
7
8
9

//01背包模板
//遍历物品数，当前遍历到的是第i件物品
    for (int i = 1; i <= n; i ++ ){
        //遍历背包容量（背包能装下的体积）（从大到小遍历）
        for (int j = m; j >= v[i]; j -- ){//[m,v[i]]
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
1
2
3
4
5
6
7
8
9

模板对比：从小到大是完全背包，从大到小是01背包，其他的一模一样！
注：多重背包也是从大到小

也就是说：只有完全背包是从大到小 巧记：“小浣熊”

备注：

//多重背包模板
//遍历每件物品
    for(int i = 0 ; i <= m ;i++)//从0开始还是从1开始，要看具体的题目
    {
        //遍历容量
        for(int j = n ; j >= 0 ;j--)
        {
            //遍历个数
            for(int k = 1 ; k *v[i] <= j && k <= s[i] ;k++)
            {
                //容量为j的方案数
                f[j] = max(f[j] , f[j-k*v[i]] + k*w[i]);
            }
        }
    }
    cout<<f[n]<<endl;//容量为n的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17