資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式查詢不超過T的最長可能時間以解決所有問題
假設我們有一個包含N個元素的陣列A。還有另一個數字T。假設Amal正在嘗試參加一個程式設計比賽。它持續T分鐘，並有N個問題。他需要A[i]時間來解決第i個問題。他將從N個問題中選擇零個或多個問題來解決，以便總共花費不超過T分鐘。我們必須找到解決他所選問題的最長時間。
因此，如果輸入類似於T = 17；A = [2, 3, 5, 7, 11]，則輸出將為17，因為如果他選擇前四個問題，則總共需要2 + 3 + 5 + 7 = 17分鐘來解決它們，這是不超過T分鐘的最長可能時間。
步驟
為了解決這個問題，我們將遵循以下步驟：
n := size of A Define an array b of size (n / 2) and c of size (n - n/2) for initialize i := 0, when i < n / 2, update (increase i by 1), do: b[i] := A[i] for initialize i := n / 2, when i < n, update (increase i by 1), do: c[i - n / 2] = A[i] Define an array B, C for bit in range 0 to 2^(n/2), increase bit after each iteration, do p := 0 for initialize i := 0, when i < n / 2, update (increase i by 1), do: if bit AND 2^i is non zero, then p := p + b[i] insert p at the end of B for bit in range 0 to 2^(n - n/2), increase bit after each iteration p := 0 for initialize i := 0, when i < n - n / 2, update (increase i by 1), do: if bit AND 2^i is non-zero, then p := p + c[i] insert p at the end of C mx := 0 sort the array C for initialize i := 0, when i < size of B, update (increase i by 1), do: if t - B[i] < 0, then: Ignore following part, skip to the next iteration itr = next larger element of (t - B[i]) in C (decrease itr by 1) mx := maximum of mx and (itr + B[i]) return mx
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
int solve(int t, vector<int> A){
int n = A.size();
vector<int> b(n / 2), c(n - n / 2);
for (int i = 0; i < n / 2; i++)
b[i] = A[i];
for (int i = n / 2; i < n; i++)
c[i - n / 2] = A[i];
vector<int> B, C;
for (int bit = 0; bit < (1 << (n / 2)); bit++){
int p = 0;
for (int i = 0; i < n / 2; i++){
if (bit & (1 << i))
p += b[i];
}
B.push_back(p);
}
for (int bit = 0; bit < (1 << (n - n / 2)); bit++){
int p = 0;
for (int i = 0; i < n - n / 2; i++){
if (bit & (1 << i))
p += c[i];
}
C.push_back(p);
}
int mx = 0;
sort(C.begin(), C.end());
for (int i = 0; i < B.size(); i++){
if (t - B[i] < 0)
continue;
auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
itr--;
mx = max(mx, *itr + B[i]);
}
return mx;
}
int main(){
int T = 17;
vector<int> A = { 2, 3, 5, 7, 11 };
cout << solve(T, A) << endl;
}輸入
17, { 2, 3, 5, 7, 11 }輸出
17
更新於: 2022年3月3日
201 次檢視
廣告