数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 递送物品的最小数量。
问题陈述
给定一个大小为 N 的数组，表示桶，每个数组索引包含项目。给定 K 次旅行，在这些旅行中，需要交付所有项目。在 1 次旅行中，只允许从一个桶中取项目。任务是告知每次旅行需要交付的最小项目数量，以便在 K 次旅行内交付所有项目。
如果有 5 个桶，项目 = {1, 3, 5, 7, 9} 和 10 次旅行，那么我们可以在每次旅行中交付 3 个项目通过一次交付 3 个项目，
第一个桶的大小为 1，因此所需的旅行次数 = 1
第二个桶的大小为 3，因此所需的旅行次数 = 1
第三个桶的大小为 5，因此所需的旅行次数 = 2（3 + 2 个项目/次旅行）
第四个桶的大小为 7，因此所需的旅行次数 = 3（3 + 3 + 1 个项目/次旅行）
第五个桶的大小为 9，因此所需的旅行次数 = 3（3 + 3 + 3 个项目/次旅行）
旅行总数 = 10
算法
1. find the minimum number of items to be distributed per delivery 2. iterate from 1 to the maximum value of items in a bucket and calculate the number of tours required for each bucket and find the total number of tours for complete delivery 3. The first such value with tours less than or equals K gives the required number
示例
#include <iostream>
#include <climits>
#include <cmath>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minItemsDeliveried(int *arr, int n, int k){
int maxElement = INT_MIN;
for (int i = 0; i < n; ++i) {
maxElement = max(maxElement, arr[i]);
}
for (int i = 1; i < maxElement + 1; ++i) {
int tours = 0;
for (int j = 0; j < n; ++j) {
if (arr[i] % i == 0) {
tours += arr[j] / i;
} else {
tours += floor(arr[j] / i) + 1;
}
}
if (tours <= k) {
return i;
}
}
return 1;
}
int main(){
int arr[] = {1, 3, 5, 7, 9};
int k = 10;
cout << "Minimum items to be delivered = " <<
minItemsDeliveried(arr, SIZE(arr), k) << endl;
return 0;
}输出
编译并执行上述程序时，它会生成以下输出：
Minimum items to be delivered = 3
更新于: 2019年10月31日
230 次浏览
广告