当前位置:   article > 正文

算法之动态规划(DP)求解完全背包问题_动态规划法求解完全背包问题

动态规划法求解完全背包问题

算法之动态规划(DP)求解01背包问题
上面这篇文章主要讲解了01背包问题和动态规划算法,如果你不了解动态规划算法,建议先浏览一下这篇文章熟悉一下,因为,本文的算法思想是基于这篇文章的。

1、什么是完全背包问题?

01背包问题:有一个背包的容积为V,有N个物品,每个物品的体积为v[i],权重为w[i],每个物品只能取1次放入背包中,背包所有物品权重和最大是多少?

完全背包 :有一个背包的容积为V,有N个物品,每个物品的体积为v[i],权重为w[i],每个物品可以取无限次放入背包中,背包所有物品权重和最大是多少?

01背包问题和完全背包问题的区别就在于,每个物品取的最大次数是1次还是无限次。

2、动态规划的状态和转移方程

参考01背包的状态和转移方程,来推导完全背包的状态和转移方程。

01背包问题的状态和转移方程:

状态: f[i][j]  选择前i个物品,体积为j时的最优方案,即所选物品的最大权重和。
状态转移:f[i][j] = max(f[i-1][j-v[i]]+w[i], f[i-1][j]) 
  • 1
  • 2
  • 3
  • 4

现在物品可以取无数次,那么f[i][j]怎么构造合适呢?
完全背包,有N个物品,背包容量V,最终求解背包的最大权重,因此,完全背包和 01背包这些都一致,因此,状态一致。f[i][j] 选择前i个物品,体积为j时的最优方案,即所选物品的最大权重和。

状态转移方程如何构造呢?
01背包问题每次增加第i物品时,因为只能取一次,从j中减去v[i],再加上w[i],这个操作只进行了一次。现在可以增加无数次,大家想想,怎么做呢?

大家可以留出5秒钟的时间来思考…

时间到,聪明的朋友肯定想到了,第i个物品可以增加0次(即f[i-1][j]),增加1次,增加2次,增加3次…增加k-1次,(这里k*v[i] > j),然后求所有值的最大值作为f[i][j]的值。
因此我们可以写出状态和状态转移方程:

状态: f[i][j]  选择前i个物品,体积为j时的最优方案,即所选物品的最大权重和。
状态转移:f[i][j] = max(f[i-1][j- k * v[i]]+ k * w[i] (k= 0, 1, 2, 3, 4,...)) 
  • 1
  • 2

恭喜你,完全背包问题已经被你攻克了,下面来看一下代码吧。

3、代码

练习题:完全背包问题

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
  • 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

程序:

白银级代码
#include<stdio.h>

int f[1050][1050];
int v[1050];
int w[1050];
int max(int a, int b)
{
    if (a > b) {
        return a;
    }
    return b;
}

int main()
{
    int n,m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &v[i], &w[i]);
    }
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i - 1][j]; 
            if (v[i] > j) {  // 防止数组越界
                continue;
            }
            for (int k = 0; k * v[i] <= j; k++) { // 添加k个物品i
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    printf("%d\n", f[n][m]);
}

  • 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
  • 35

代码优化

作为一个研究算法的coding farmer,不对算法精益求精的进行优化,那就不叫学习算法。
如果你是高手,肯定发现了上面代码中有很多可以优化的地方,不妨花3分钟尝试找一下优化点吧。

优化点:

黄金级:
1)if (v[i] > j) 可以优化到 for (int j = 1; j <= m; j ++ ) 中,优化后为:

 for (int j = v[i]; j <= m; j ++ )  {
	......
 }
  • 1
  • 2
  • 3

2)w[] 和 v[]可以优化掉。代码中的v和w数组使用仅限于i状态下,因此,可以定义两个变量,v和w,在for (int i = 1; i <= n; i ++ )中输入即可,优化后:
for (int i = 1; i <= n; i ++ ) {
int v, w;
scanf("%d %d", &v, &w);
}

铂金级
二维数组f可以优化成一维的f,具体优化可以参考这篇文章,这里不过多介绍。

王者级:
从状态转移方程下手:f[i][j] = max(f[i-1][j- k * v[i]]+ k * w[i] (k= 0, 1, 2, 3, 4,…))
方程拆开:

f[i][j] = max(f[i-1][j],  f[i-1][j - v[i]]+w[i], f[i-1][j-2*v[i]]+2*w[i], f[i-1][j-3*v[i]]+3*w[i] ,......)
  • 1

使用代入法,将j= j-v[i]带入上面的方程中得到:

f[i][j-v[i]] = max(f[i-1][j-v[i]],  f[i-1][j - 2*v[i]]+w[i], f[i-1][j-3*v[i]]+2*w[i], f[i-1][j-3*v[i]]+3*w[i] ,......)
  • 1

对比第二个和第一个方程,我们发现,方程1可以简化成:

f[i][j] = max(f[i-1][j],  f[i][j - v[i]] + w[i])
  • 1

怎么看起来跟01背包模型的好像啊,我们对比一下:

f[i][j] = max(f[i-1][j],  f[i-1][j - v[i]] + w[i])  // 01背包
f[i][j] = max(f[i-1][j],  f[i  ][j - v[i]] + w[i])   // 完全背包
  • 1
  • 2

发现了区别在下标从i-1变为i。为什么呢?
f[i][j - v[i]] 已经将除去1个物品i时的所有最优解已经求出来了,因此在计算f[i][j]时,无需再重复计算k=2,3,4,5…时的值了。

好了,上最终的代码了:

#include<stdio.h>
int f[1050];
int main()
{
    int n,m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ ) {
        int v,w;
        scanf("%d %d", &v, &w);
        for (int j = v; j <= m; j++ ) {
            f[j] = (f[j] > f[j - v] + w) ? f[j] :f[j - v] + w;
        }
    }
    printf("%d\n", f[m]);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

16行代码解决该问题,如果有疑问或者不懂的地方欢迎评论区留言。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/432255
推荐阅读
相关标签
  

闽ICP备14008679号