資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告