c++ - 如何找到添加两个变量的所有可能组合,每个变量都附加到一个乘数,总和为给定数字(cin)?
问题描述
在我的情况下,一辆货车的容量为 30,而货车的容量为 10。我需要找到运输给定数量货物所需的货车/货车的数量,比如 100。我需要找到所有可能的组合卡车 + 货车加起来 100 辆。
基本的数学计算是:(30*lorrycount) + (10*vancount) = n,其中 n 是货物数量。
输出示例
运输货物:100
货车数量:0 3 2 1
货车数量:10 1 4 7
例如,第二个组合是 3 辆货车,1 辆面包车。考虑到货车的容量 = 30,货车容量 = 10,(30*3)+(10*1) = 100 = n。
目前,我们只有这个代码,它可以找到所有加起来等于给定数字 n 的数字组合,而不考虑上面给出的公式。
#include <iostream>
#include <vector>
using namespace std;
void findCombinationsUtil(int arr[], int index,
int num, int reducedNum)
{
int lorry_capacity = 30;
int van_capacity = 10;
// Base condition
if (reducedNum < 0)
return;
// If combination is found, print it
if (reducedNum == 0)
{
for (int i = 0; i < index; i++)
cout << arr[i] << " ";
cout << endl;
return;
}
// Find the previous number stored in arr[]
// It helps in maintaining increasing order
int prev = (index == 0) ? 1 : arr[index - 1];
// note loop starts from previous number
// i.e. at array location index - 1
for (int k = prev; k <= num; k++)
{
// next element of array is k
arr[index] = k;
// call recursively with reduced number
findCombinationsUtil(arr, index + 1, num,
reducedNum - k);
}
}
void findCombinations(int n)
{
// array to store the combinations
// It can contain max n elements
std::vector<int> arr(n); // allocate n elements
//find all combinations
findCombinationsUtil(&*arr.begin(), 0, n, n);
}
int main()
{
int n;
cout << "Enter the amount of cargo you want to transport: ";
cin >> n;
cout << endl;
//const int n = 10;
findCombinations(n);
return 0;
}
如果您对此有任何解决方案,请告诉我,谢谢。
解决方案
我们将创建一个递归函数,capacities
从左到右遍历一个全局数组,并尝试将货物加载到各种车辆类型中。我们跟踪我们仍然需要加载多少并将其传递给任何递归调用。如果我们到达数组的末尾,则仅当剩余货物为零时才产生解决方案。
std::vector<int> capacities = { 30, 10 };
using Solution = std::vector<int>;
using Solutions = std::vector<Solution>;
void tryLoad(int remaining_cargo, int vehicle_index, Solution so_far, std::back_insert_iterator<Solutions>& solutions) {
if (vehicle_index == capacities.size()) {
if (remaining_cargo == 0) // we have a solution
*solutions++ = so_far;
return;
}
int capacity = capacities[vehicle_index];
for (int vehicles = 0; vehicles <= remaining_cargo / capacity; vehicles++) {
Solution new_solution = so_far;
new_solution.push_back(vehicles);
tryLoad(remaining_cargo - vehicles * capacity, vehicle_index + 1, new_solution, solutions);
}
}
如下调用它应该产生所需的输出all_solutions
:
Solutions all_solutions;
auto inserter = std::back_inserter(all_solutions)
tryLoad(100, 0, Solution{}, inserter);
推荐阅读
- webpack - 为什么 Webpack 中没有设置环境
- spring-mvc - Spring Boot 2 的侵入性 AsyncRequestTimeoutException
- python - 在 python 中使用 mplayer 从 websoket 播放音频延迟 4 到 5 秒
- python - 使用 cv2 时关闭 Python 文件
- swift - 将 csv 文件从 Apple Watch 发送到手机 - 没有任何反应
- android - 片段中的线程只调用一次
- javascript - JS Contenteditable 下划线不起作用
- javascript - Django 在模板中向 Javascript 发送数据
- google-sheets - 如何使用从列中查找字符串,然后使用它进行 vlookup - Google 表格
- anaconda - 从 conda cloud 访问旧的 pytorch 版本