前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【动态规划/背包问题】完全背包求方案数

【动态规划/背包问题】完全背包求方案数

作者头像
宫水三叶的刷题日记
发布2021-10-20 16:17:29
1.1K0
发布2021-10-20 16:17:29
举报

前言

今天是我们讲解「动态规划专题」中的「背包问题」的第二十篇

今天将学习「背包问题求具体方案」问题。

另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。

你可以先尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的「1449. 数位成本和为目标值的最大数字」,难度为 「困难」

Tag : 「完全背包」、「背包问题」、「动态规划」

给你一个整数数组

cost

和一个整数

target

。请你返回满足如下规则可以得到的 最大 整数:

  • 给当前结果添加一个数位
(i + 1)

的成本为

cost[i]

cost

数组下标从

0

开始)

  • 总成本必须恰好等于
target
  • 添加的数位中没有数字
0

由于答案可能会很大,请你以字符串形式返回。

如果按照上述要求无法得到任何整数,请你返回 "0" 。

示例 1:

代码语言:javascript
复制
输入:cost = [4,3,2,5,6,7,2,5,5], target = 9

输出:"7772"

解释:添加数位 '7' 的成本为 2 ,添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字,但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2:

代码语言:javascript
复制
输入:cost = [7,6,5,5,5,6,8,7,8], target = 12

输出:"85"

解释:添加数位 '8' 的成本是 7 ,添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3:

代码语言:javascript
复制
输入:cost = [2,4,6,2,4,6,4,4,4], target = 5

输出:"0"

解释:总成本是 target 的条件下,无法生成任何整数。

示例 4:

代码语言:javascript
复制
输入:cost = [6,10,15,40,40,40,40,40,40], target = 47

输出:"32211"

提示:

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000

基本分析

根据题意:给定

1

~

9

几个数字,每个数字都有选择成本,求给定费用情况下,凑成的最大数字是多少。

通常我们会如何比较两数大小关系?

首先我们 根据长度进行比较,长度较长数字较大;再者,对于长度相等的数值,从高度往低位进行比较,找到第一位不同,不同位值大的数值较大。

其中规则一的比较优先级要高于规则二。

基于此,我们可以将构造分两步进行。

完全背包 + 贪心

具体的,先考虑「数值长度」问题,每个数字有相应选择成本,所能提供的长度均为

1

问题转换为:有若干物品,求给定费用的前提下,花光所有费用所能选择的最大价值(物品个数)为多少。

每个数字可以被选择多次,属于完全背包模型。

当求得最大「数值长度」后,考虑如何构造答案。

根据规则二,应该尽可能让高位的数值越大越好,因此我们可以从数值

9

开始往数值

1

遍历,如果状态能够由该数值转移而来,则选择该数值。

代码:

代码语言:javascript
复制
class Solution {
    public String largestNumber(int[] cost, int t) {
        int[] f = new int[t + 1];
        Arrays.fill(f, Integer.MIN_VALUE);
        f[0] = 0;
        for (int i = 1; i <= 9; i++) {
            int u = cost[i - 1];
            for (int j = u; j <= t; j++) {
                f[j] = Math.max(f[j], f[j - u] + 1);
            }
        }
        if (f[t] < 0) return "0";
        String ans = "";
        for (int i = 9, j = t; i >= 1; i--) {
            int u = cost[i - 1];
            while (j >= u && f[j] == f[j - u] + 1) {
                ans += String.valueOf(i);
                j -= u;
            }
        }
        return ans;
    }
}
  • 时间复杂度:
O(n * t)
  • 空间复杂度:
O(t)

思考 & 进阶

懂得分两步考虑的话,这道题还是挺简单。虽然是「DP」+「贪心」,但两部分都不难。

其实这道题改改条件/思路,也能衍生出几个版本:

  1. 【思考】如何彻底转化为「01 背包」或者「多重背包」来处理? 完全背包经过一维优化后时间复杂度为
O(N * C)

。是否可以在不超过此复杂度的前提下,通过预处理物品将问题转换为另外两种传统背包?

  • 对于「多重背包」答案是可以的。由于给定的最终费用
t

,我们可以明确算出每个物品最多被选择的次数,可以在

O(N)

的复杂度内预处理额外的

s[]

数组。然后配合「单调队列优化」,做到

O(N * C)

复杂度,整体复杂度不会因此变得更差。 但转换增加了「预处理」的计算量。为了让转换变成“更有意义”,我们可以在「预处理」时顺便做一个小优化:对于相同成本的数字,只保留数值大的数字。不难证明,当成本相同时,选择更大的数字不会让结果变差。

  • 对于「01 背包」答案是不可以。原因与「多重背包」单纯转换为「01 背包」不会降低复杂度一致。因此本题转换成「01 背包」会使得
N

发生非常数级别的增大。

  1. 【进阶】不再是给定数值
1

~

9

(取消

cost

数组),转为给定

nums

数组(代表所能选择的数字,不包含

0

),和相应

price

数组(长度与

nums

一致,代表选择

nums[i]

所消耗的成本为

price[i]

)。现有做法是否会失效? 此时

nums

中不再是只有长度为

1

的数值了。但我们「判断数值大小」的两条规则不变。因此「第一步」不需要做出调整,但在进行「第二步」开始前,我们要先对物品进行「自定义规则」的排序,确保「贪心」构造答案过程是正确的。规则与证明都不难请自行思考。

  1. 【进阶】在进阶
1

的前提下,允许

nums

出现

0

,且确保答案有解(不会返回答案

0

),该如何求解? 增加数值

0

其实只会对最高位数字的决策产生影响。 我们可以 通过预处理转换为「分组 & 树形」背包问题:将

nums

中的非

0

作为一组「主件」(分组背包部分:必须选择一个主件),所有数值作为「附属件」(树形背包部分:能选择若干个,选择附属件必须同时选择主件)。

背包问题(目录)

  1. 01背包 : 背包问题 第一讲
    1. 【练习】01背包 : 背包问题 第二讲
    2. 【学习&练习】01背包 : 背包问题 第三讲
  2. 完全背包 : 背包问题 第四讲
    1. 【练习】完全背包 : 背包问题 第五讲
    2. 【练习】完全背包 : 背包问题 第六讲
    3. 【练习】完全背包 : 背包问题 第七讲
  3. 多重背包 : 背包问题 第八讲
  4. 多重背包(优化篇)
    1. 【上】多重背包(优化篇): 背包问题 第九讲
    2. 【下】多重背包(优化篇): 背包问题 第十讲
  5. 混合背包 : 背包问题 第十一讲
  6. 分组背包 : 背包问题 第十二讲
    1. 【练习】分组背包 : 背包问题 第十三讲
  7. 多维背包
    1. 【练习】多维背包 : 背包问题 第十四讲
    2. 【练习】多维背包 : 背包问题 第十五讲
  8. 树形背包 : 背包问题 第十六讲
    1. 【练习篇】树形背包 : 背包问题 第十七讲
    2. 【练习篇】树形背包 : 背包问题 第十八讲
  9. 背包求方案数
    1. 【练习】背包求方案数 : 背包问题 第十九讲
    2. 【练习】背包求方案数
  10. 背包求具体方案
    1. 【练习】背包求具体方案:本篇
  11. 泛化背包
    1. 【练习】泛化背包
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-10-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 题目描述
  • 基本分析
  • 完全背包 + 贪心
  • 思考 & 进阶
  • 背包问题(目录)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档