2024华为OD面试手撕代码真题 - 最大的礼物价值

华为OD面试真题精选

专栏：华为OD面试真题精选
目录: 2024华为OD面试手撕代码真题目录以及八股文真题目录

问题描述

在某个商店中，有许多礼物可供选择，每个礼物都有一个固定的价值。这些礼物的价值可能会有重复。你的任务是从这些礼物中选择三个不同的礼物，使得它们的总价值不超过100。在这种限制下，求出总价值不超过100的最大价值。

假设商店中有以下礼物及其对应的价值：

礼物A：价值20
礼物B：价值50
礼物C：价值30
礼物D：价值70
礼物E：价值60
礼物F：价值80
礼物G：价值90
礼物H：价值40
要从这些礼物中选择三个不同的礼物，并且它们的总价值不超过100。

01背包问题思路：

可以使用01背包问题的思路来解决这个问题。01背包问题是一个经典的动态规划问题，可以用来解决选择礼物的问题。

1. 状态定义：

   • 定义 dp[i][j] 表示在前 i 个礼物中选择若干个礼物，使得总价值不超过 j 时的最大总价值。

2. 状态转移：

   • 如果不选第 i 个礼物：dp[i][j] = dp[i-1][j]
   • 如果选第 i 个礼物：dp[i][j] = dp[i-1][j-gifts[i-1]] + gifts[i-1]
   • 综合考虑：dp[i][j] = max(dp[i-1][j], dp[i-1][j-