完全背包问题

Kubrnete 等级 806 1 0

问题描述

有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v[i],体积为w[i],求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?

跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可以选择任意多件。从每件物品的角度来说,与之相关的策略已经不再是选或者不选了,而是有取0件、取1件、取2件...直到取⌊c/wi⌋(向下取整)件。

在上一篇文章中,我们提到过01背包问题的递推关系:

完全背包问题

认识01背包问题之后,现在让我们来看对于完全背包问题的递归解法:

完全背包的递推关系

我们用V_total(i,j)表示前i种物品放入一个容量为j时的背包获得的最大价值,那么对于第i种物品,我们有k种选择,0 <= k * w[i] <= j,(容量约束条件)即可以选择0、1、2...k件第i种物品,所以递推表达式为:

V_total(i,j) = max{V_total(i-1, j - w[i] * k) + v[i] * k}; (0 <= k * w[i] <= j)

(注:当k=0则为不选,最多可选k=j/w[i]件。在这个范围中找出k种选择种的最优解)

现在我们很容易能够写出对应的递归代码。

理所当然地,我们将用一个数组存储计算结果,如果递归时已经计算过,那么返回该结果。

int V_total(int i, int j)
{
    int value = 0;
    if (i && j) //可选物品个数和初始容量皆不为0
    { 
        if (j < w[i])
            value = V_total(i - 1, j);
        else
            for (int k = 0; k * w[i] <= j; k++)
            {
                int temp = V_total(i - 1, j - w[i] * k) + v[i] * k;
                value = temp > value ? temp : value;
            }
    }
    return value;
}

填表法

当然,有了这个递推关系式,其实也是我们的状态转移方程式,现在我们可以尝试用填表的方式自下而上处理。

比如只有两个物品:物品A:价值5,体积5,物品B:价值8:体积7,背包容量为10,下面开始填表。

完全背包问题

物品1重量V=5,价值P=5,物品2重量V=7,价值P=8。可选物品个数为0和容量为0的选择都为0。

i=1时,若t<10,背包最多只能放下1个物品1,价值为5;当t=10时,能放下2个物品1,因此i=1时的最大值为10。

i=2时,若5<=t<7时,背包能放下1个物品1;当7<=t<10时,背包能放下1个物品2,最大值为8;当t=10时,能放下2个物品1或1个物品2,因此最大值为10。通过求解这些子问题的最优解,我们推导出了全局最优解。

转换代码如下

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= c; j++)
        for (int k = 0; k * w[i] <= j; k++)
            values[i + 1][j] = max(values[i + 1][j], values[i][j - k * w[i]] + k * v[i]);
cout << values[n][c];

和01背包一样,这里效率仍可以继续优化。具体思路这里就不重复介绍了,可以翻看前面的01背包问题动态规划篇。

优化后的状态转移方程为:

V_total(t) = max{V_total(t), V_total(t - wi) + vi}

附完整代码:

#include <bits/stdc++.h>
using namespace std;
int n, c, d;
int v[1002], w[1002], dp[1002];
int main()
{

    cin >> n >> c;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    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];
}

其实完全背包问题也可以转化成01背包问题来求解。因为第i件物品最多选 ⌊c/wi⌋(向下取整) 件,于是可以把第i种物品转化为

体积 j=⌊c/wi⌋件价值相同的物品,然后再对这个01背包问题进行求解。具体留给大家自行解决。如果遇到问题,可以翻开前面关于01背包问题的两篇文章。

总结

完全背包问题跟01背包有很多相似之处,比较一下他们的状态转移方程以及各种解法,就会发现他们其实是异父异母的亲兄弟。

(建议仔细思考其中的区别)

它们的本质区别就是01背包从体积大的开始遍历,这样的话就不能一件物品多次放置。而完全背包是从体积最小的开始遍历,这样的话就会出现一件物品多次放置的特点。这样也就凸显了两种背包的不同,但是这两种都是最基本的背包雏形。

这两个背包问题的关键都在于状态转移方程的寻找,如果对于类似的问题没有思路,可以先尝试找出递归解法,然后自上而下的记忆法便水到渠成了。

当然,最重要的还是解题思路,理解记忆法和填表法的精髓,有助于之后举一反三,去解决类似的延伸问题。

本文转自 https://blog.csdn.net/guanguandaren/article/details/107960802,如有侵权,请联系删除。

收藏
评论区

相关推荐

C++概述
概述 C 是静态,可编译,通用,大小写敏感,格式自由的编程语言,它支持程序化,面向对象的,和泛型编程方式。 C 被看作是中间层语言,因为它同时包含了低级语言和高级语言的特性。 C 是于 1979 年在新泽西的茉莉山丘的贝尔实验室由 Bjarne Stroustrup 开发的,它是 C 语言的加强版,最开始它被称作 “C with Classes”,但是
C++ 基本语法
C 程序可以定义为对象的集合,这些对象通过调用彼此的方法进行交互。现在让我们简要地看一下什么是类、对象,方法、即时变量。 对象 对象具有状态和行为。例如:一只狗的状态 颜色、名称、品种,行为 摇动、叫唤、吃。对象是类的实例。 类 类可以定义为描述对象行为/状态的模板/蓝图。 方法 从基本上说,一个方法表示一种行为。一个类可以包含多个
c++11 实现单例模式
C11出来后,里面新增加了好多好用的功能 下面的单例就是使用了C11中的标准库中的mutex和unique_prt 进行内存管理的. 此单例模式不用担心内存的释放问题 pragma once include <memory include <mutex template <class T class Singleton { public: ty
C语言_练习题(一)
前言: 看懂理解代码很容易,难的是把所理解的融会贯通,融合到实例中,你会发现事实和理论会有些许差别,编写实例能更好的帮你积累经验。 0x1 编写一个程序,要求提示输入一个ASCII码值(如,66),然后打印输入的字符。 代码: include <stdio.h int main(){ char i; printf("请输入一个ASCI
我的C语言基础
C语言32个关键字auto 声明自动变量short 声明短整型变量或函数int 声明整型变量或函数long 声明长整型变量或函数float 声明浮点型变量或函数double 声明双精度变量或函数char 声明字符型变量或函数struct 声明结构体变量或函数union 声明共用数据类型enum 声明枚举类型typedef 用以给数据类型取别名co
C语言基础习题50例(一)1-5
虎为百兽尊,罔敢触其怒。惟有父子情,一步一回顾。 习题1 有 1 、 2 、 3 、 4 个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?实现思路:显然,这个题目需要用到循环,并且是循环嵌套,先列出所有可能的组合,再去掉重复的组合即可。代码如下:cinclude <stdio.hint main(){ int i, j, k,
游戏安全实践的一些思考
移动的游戏能够稳定健康的上线。主要需要依赖以下在四个方面:1.前端展示,或者说客户端正常运行。性能稳定不崩溃,不过热能够稳定运行。2.后端,或者游戏后台服务端的。不但要稳定。还有能在有限的服务器资源下,能承受大量的同时在线用户。而且要让游戏中的每个模块都能够承受承受大量的同时在线用户。3.安全也是重点之中。这既包括客户端,又包括服务端。客户端的安全,包括要防
C 如何判断编译器是否支持C90 C99?
参考:《C Primer Plus》,Stephen Prata著,姜佑译。 ANSI/ISO C标准 美国ANSI成立委员会X3J11,于89/90年,99年,11年,发布C标准:C89/C90,C99,C11。 **ANSI/ISO 各版本C标准** **C标准** **描述** 经典C 也称K&R C,87年K&R著作《C语言程序设计》,
C++
第一眼见到explicit和volatile可能会一愣一愣的觉得可能是c11或者c14新加的标识符。 其实不是这样,volatile和const两个关键字在C语言的第二个版本KR C的时候就被加入了C标准,他们是两个相对的关键字 const 修饰符表示这是一个常量类型,这个变量的值不会被程序改变 volatile 修饰符表示这个
C++11新特性学习
1、什么是C+11 ========= C++11标准为C++编程语言的第三个官方标准,正式名叫ISO/IEC 14882:2011 - Information technology -- Programming languages -- C++。在正式标准发布前,原名C++0x。它将取代C++标准第二版ISO/IEC 14882:2003 - Progr
C++学习_从C到C++
### 一、引用的概念和应用 * * * ####  1.引用的概念 下面写法定义了一个引用,并将其初始化为引用某个变量。 类型名 & 引用名 = 某变量名; int n = 4; int & r = n; // r引用了n,r的类型是 int & 某个变量的引用,等价于这个变量,相当于该变量的一个别
C++学习建议
// 转载 C++学习建议 C++缺点之一,是相对许多语言复杂,而且难学难精。许多人说学习C语言只需一本K&R《C程序设计语言》即可,但C++书籍却是多不胜数。我是从C进入C++,皆是靠阅读自学。在此分享一点学习心得。个人认为,学习C++可分为4个层次: 第一层次:C++基础:挑选一本入门书籍,如《C++ Primer》、《C++大学教程》、或Stro
4.python
#一 > **编写一个函数判断输入的三个数是否能构成三角形** **我写的函数** def is_triangle(a, b, c): if (a+b>c and abs(a-b)<c) or (a+c>b and abs(a-c)<b) or (b+c>a and abs(b-c)<a): return
C++ Modern C++
        现代的C++,比较笼统。最近10多年的东西是否是现代的呢?我认为“时髦”这个词更准确一些。每个年代,时髦总是标新立异的,总是被年龄大一些的人看不惯的(虽然这些人也曾经“赶过时髦”)。Modern C++就是用最时髦的东西去装饰您的代码。但是本质的东西还是没有变。改革初期,最时髦的服饰是喇叭裤,霹雳舞手套。那时没有智能手机,时髦的人扛着一台卡带
Emacs 学习笔记
1.  C-v  向下翻页 2.  M-v 向上翻页 3.  C-l   将光标位居中 4.  C-n  下一行 next 5.  C-p  上一行 previous 6.  C-b   光标backward 7.  C-f    光标forward 8.  M-f