0，1背包最大价值问题、最少步数归零问题

目录

一、0，1背包最大价值问题

问题描述

测试样例

 解题思路：

问题理解

数据结构选择

算法步骤

最终代码： 

运行结果：

​编辑 

二、最少步数归零问题 

问题描述

测试样例

解题思路：

问题理解

数据结构选择

算法步骤

关键点

 最终代码：

运行结果： 

一、0，1背包最大价值问题

问题描述

一个旅行者外出旅行时需要将 n 件物品装入背包，背包的总容量为 m。每个物品都有一个重量和一个价值。你需要根据这些物品的重量和价值，决定如何选择物品放入背包，使得在不超过总容量的情况下，背包中物品的总价值最大。

给定两个整数数组 weights 和 values，其中 weights[i] 表示第 i 个物品的重量，values[i] 表示第 i 个物品的价值。你需要输出在满足背包总容量为 m 的情况下，背包中物品的最大总价值。

测试样例

样例1：

输入：n = 3 ,weights = [2, 1, 3] ,values = [4, 2, 3] ,m = 3
输出：6

样例2：

输入：n = 4 ,weights = [1, 2, 3, 2] ,values = [10, 20, 30, 40] ,m = 5
输出：70

样例3：

输入：n = 2 ,weights = [1, 4] ,values = [5, 10] ,m = 4
输出：10

 解题思路：

问题理解

这是一个经典的0/1背包问题，目标是选择一些物品放入背包，使得在不超过背包容量的情况下，背包中物品的总价值最大。

数据结构选择

我们可以使用动态规划（Dynamic Programming, DP）来解决这个问题。动态规划的核心思想是将问题分解为子问题，并存储子问题的解以避免重复计算。

算法步骤

1. 定义状态：

   • 使用一个二维数组 dp[i][j]，其中 i 表示前 i 个物品，j 表示背包的容量。dp[i][j] 表示在前 i 个物品中选择物品放入容量为 j 的背包中所能获得的最大价值。

2. 状态转移方程：

   • 对于每个物品 i，我们有两种选择：
     • 不放入背包：dp[i][j] = dp[i-1][j]
     • 放入背包：dp[i][j] = dp[i-1][j - weights[i-1]] + values[i-1]（前提是 j >= weights[i-1]）
   • 因此，状态转移方程为：

     plaintext

     dp[i][j] = max(dp[i-1][j], 

     dp[i-1][j - weights[i-1]] + 

     values[i-1])  if j >= 

     weights[i-1]

     dp[i][j] = dp[i-1][j]  if j 

     < weights[i-1]

3. 初始化：

   • dp[0][j] = 0 表示没有物品时，无论背包容量是多少，最大价值都是0。
   • dp[i][0] = 0 表示背包容量为0时，无论有多少物品，最大价值都是0。

4. 最终结果：

   • 最终答案就是 dp[n][m]，即在前 n 个物品中选择物品放入容量为 m 的背包中所能获得的最大价值。

最终代码： 

def solution(n: int, weights: list, values: list, m: int) -> int:
    # 初始化dp数组
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 填充dp数组
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if j >= weights[i - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]
    
    # 返回最大价值
    return dp[n][m]

if __name__ == '__main__':
    print(solution(n = 3, weights = [2, 1, 3], values = [4, 2, 3], m = 3) == 6)
    print(solution(n = 4, weights = [1, 2, 3, 2], values = [10, 20, 30, 40], m = 5) == 70)
    print(solution(n = 2, weights = [1, 4], values = [5, 10], m = 4) == 10)

运行结果：

二、最少步数归零问题 

问题描述

小R拿到了一个长度为n的数组，其中每个元素都是一个正整数。小R发现每次可以删除某个数组中某个数的一位数字，这样可以逐步将所有数字变为0。他想知道，要将数组中所有数字都变为0，最少需要多少步？

例如：对于数字 103，小R可以选择删除第1位数字，将其变为 3；或者删除第2位数字，变为 13，又或者删除第3位数字，将其变为 10。最终目标是将所有数字都删除为0。

测试样例

样例1：

输入：n = 5,a = [10, 13, 22, 100, 30]
输出：7

样例2：

输入：n = 3,a = [5, 50, 505]
输出：4

样例3：

输入：n = 4,a = [1000, 1, 10, 100]
输出：4

解题思路：

问题理解

你需要计算将数组中所有数字变为0所需的最少步数。每一步可以删除某个数字的一位数字。

数据结构选择

• 数组 a 存储了所有需要处理的数字。
• 每个数字可以转换为字符串来处理每一位。

算法步骤

1. 单个数字的处理：

   • 对于每个数字，计算将其变为0所需的最少步数。
   • 如果数字是0，不需要任何步数。
   • 如果数字是个位数，只需要一步。
   • 对于其他数字，计算非0数字的个数，因为每个非0数字都需要一步来删除。

2. 数组的处理：

   • 遍历数组中的每个数字，调用单个数字的处理函数，累加步数。

关键点

• 如何高效地计算每个数字的非0位数。
• 如何累加所有数字的步数。

 最终代码：

def min_steps_for_number(num: int) -> int:
    """计算单个数字归零需要的最少步数"""
    # 如果是0，不需要任何步数
    if num == 0:
        return 0
    
    # 如果是个位数，只需要一步
    if num < 10:
        return 1
    
    # 将数字转为字符串以便处理每一位
    str_num = str(num)
    length = len(str_num)
    
    # 对于每个非0数字，我们都需要一步来删除它
    # 计算非0数字的个数
    non_zero_count = sum(1 for digit in str_num if digit != '0')
    
    return non_zero_count

def solution(n: int, a: list) -> int:
    """计算数组中所有数字归零的最少步数总和"""
    # 对数组中每个数字计算最少步数并求和
    total_steps = 0
    for num in a:
        steps = min_steps_for_number(num)
        total_steps += steps
    
    return total_steps

if __name__ == '__main__':
    # 测试样例
    print(solution(5, [10, 13, 22, 100, 30]) == 7)  # True
    print(solution(3, [5, 50, 505]) == 4)  # True
    print(solution(4, [1000, 1, 10, 100]) == 4)  # True
    
    # 额外测试用例
    print(solution(1, [0]) == 0)  # 测试0的情况
    print(solution(2, [9, 99]) == 3)  # 测试不同位数的情况
    print(solution(1, [101]) == 2)  # 测试中间有0的情况

运行结果：