首页 > 试题广场 >

求正数数组的最小不可组成和

[编程题]求正数数组的最小不可组成和
  • 热度指数：3685 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max； 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成和； 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = {3,2,5} arr的min为2，max为10，在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和； arr = {3,2,4} arr的min为2，max为9，在区间[2,9]上，8是不能被任何一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1，max为6，在区间[2,6]上，任何数都可以被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。
算法知识视频讲解
开通博客
头像 For.dream
发表于 2021-06-26 16:29:04
问题描述 给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？ 解题思路 01背包问题是一个非常经典的动态规划问题，可以很好的入门动态规划，与之相关的变形题目也是非 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 哈哈哈哈鹅
发表于 2022-03-29 11:17:35
   先找到数组中的最小值min，以及元素最大和add；     按照0/1背包问题，我们可以列出如下表格：     j表示组成和也就是背包的容量的组成情况，a[i]表示前i个物品任意选放的最大价值，i表示物品下标，dp[j]表示背包容量为 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 数组 2015 百度 查找 Java工程师
来自：百度 2015实习内推...
难度：
23条回答 16501浏览

热门推荐

通过挑战的用户

相关试题

求正数数组的最小不可组成和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号