我需要在c++中创建一个函数,返回最大值的索引。无论何时调用它,它都应该跳过之前返回的索引,并返回存储下一个最大值的索引。
例如,如果:-
int a[8]={2,6,4,12,5,7,12,8}
函数应该返回3,然后返回6,然后返回7,5,1,4,2,0
编辑:-
#include <iostream>
#include <vector>
using std::vector;
int return_max_index(vector<int> valuebyweight, int n)
{
int max_index = 0;
for(int i=0; i<n; i++)
{
if(valuebyweight[i] >= valuebyweight[max_index])
{
max_index = i;
}
}
return max_index;
}
double get_optimal_value(int capacity, vector<int> weights, vector<int> values,int n) {
double value = 0.0;
vector<int> valuebyweight(n);
for(int i=0; i<n; i++)
{
valuebyweight[i] = values[i] / weights[i];
}
while(capacity!=0)
{
int max_index = return_max_index(valuebyweight, n);
if(weights[max_index] <= capacity)
{
capacity -= weights[max_index];
value += values[max_index];
}
else
{
value += (valuebyweight[max_index] * capacity);
capacity = 0;
}
}
return value;
}
int main() {
int n;
int capacity;
std::cin >> n >> capacity;
vector<int> values(n);
vector<int> weights(n);
for (int i = 0; i < n; i++) {
std::cin >> values[i] >> weights[i];
}
double optimal_value = get_optimal_value(capacity, weights, values,n);
std::cout.precision(10);
std::cout << optimal_value << std::endl;
return 0;
}
尝试实现分数背包算法。如果我在输入上运行代码
3 50
60 20
100 50
120 30
它应该给出180的答案,但它返回200,因为我的"return_max_index"函数再次返回相同的索引(2)。
试试这个代码。我做了一些小改动。
#include <iostream>
#include <vector>
using std::vector;
int return_max_index(vector<int> valuebyweight, int n)
{
int max_index = 0;
for(int i=0; i<n; i++)
{
if(valuebyweight[i] >= valuebyweight[max_index])
{
max_index = i;
}
}
//if all the values in valuebyweight are 0
if(valuebyweight[max_index]==0)
{
return -1;
}
else
return max_index;
}
double get_optimal_value(int capacity, vector<int> weights, vector<int> values,int n) {
double value = 0.0;
vector<int> valuebyweight(n);
for(int i=0; i<n; i++)
{
valuebyweight[i] = values[i] / weights[i];
}
while(capacity!=0)
{
int max_index = return_max_index(valuebyweight, n);
if(max_index==-1)
{
break;
}
if(weights[max_index] <= capacity)
{
capacity -= weights[max_index];
value += values[max_index];
// assign valuebyweight[max_index] to 0 as it already participated in optimal solution and need no longer to participate.
valuebyweight[max_index]=0;
}
else
{
value += (valuebyweight[max_index] * capacity);
capacity = 0;
}
}
return value;
}
int main() {
int n;
int capacity;
std::cin >> n >> capacity;
vector<int> values(n);
vector<int> weights(n);
for (int i = 0; i < n; i++) {
std::cin >> values[i] >> weights[i];
}
double optimal_value = get_optimal_value(capacity, weights, values,n);
std::cout.precision(10);
std::cout << optimal_value << std::endl;
return 0;
}
实现这一点的一种方法是将找到的索引列表保持在静态本地。但是,你怎么知道你以前没有看过这部电影呢?所以最好把它变成一门课。然后,您还可以进行一些优化:对数组进行一次排序,然后在调用时从结果中弹出下一个最高索引:
struct mysort{
const std::vector<int>& _tosort;
mysort(const std::vector<int> tosort) : _tosort(tosort) {}
bool operator()(int a, int b){ return _tosort[a] < _tosort[b]; }
}
class IndexFinder{
private:
std::vector<int> sorted_indices;
int invoked;
public:
IndexFinder(const std::vector<int>& tosort) :
sorted_indices(tosort.size()) {
invoked = 0;
for(size_t i=0; i<tosort.size(); ++i)
sorted_indices[i] = i;
std::stable_sort(sorted_indices.begin(), sorted_indices.end(),
mysort(tosort));
}
int IndexFinder::operator()(){
return sorted_indices[invoked++];
}
};
您应该对IndexFinder::operator()()进行保护,以处理如果用户调用它的次数超过向量中的索引数时会发生什么。作为奖励,您应该能够很容易地将其更改为模板类,以对int以外的内容进行排序。
这并不漂亮(它修改了数组),但给出了一个想法:
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
int index_of_largest(int array[], size_t len) {
int r = INT_MIN;
int d = 0;
for (int i = 0; i < len; i++) {
if (array[i] > r) {
d = i;
r = array[i];
}
}
if (r != INT_MIN) {
array[d] = INT_MIN;
}
return d;
}
int main(){
int a[8] = {2, 6, 4, 12, 5, 7, 12, 8};
int len = (int)(sizeof(a) / sizeof(a[0]));
for (int i = 0; i < len; i++) {
printf("%dn", index_of_largest(a, len));
}
}
输出
3
6
7
5
1
4
2
0
这与@bloer给出的上一个答案有点不同,但通过使用C++11(std::iota
和std::sort
中的use if lambda),显示了一个更短的方法(它仍然使用一个类)。
#include <algorithm>
#include <iostream>
#include <vector>
class MaxIndex
{
private:
std::vector<int> index;
public:
MaxIndex(const std::vector<int>& tosort) : index(tosort.size())
{
// initialize the indices
std::iota(index.begin(), index.end(), 0);
// sort the indices based on passed-in vector
std::sort(index.begin(), index.end(), [&](int n1, int n2)
{ return tosort[n1] > tosort[n2];});
}
// return the nth highest index
int getNthMaxIndex(int n) const { return index[n]; }
};
using namespace std;
int main()
{
std::vector<int> a = {2,6,4,12,5,7,12,8};
MaxIndex mi(a);
for (size_t i = 0; i < a.size(); ++i)
cout << mi.getNthMaxIndex(i) << endl;
}
实际示例
其次,如果要使用std::vector
,是否有理由持续使用n
?std::vector
知道自己的大小,因此传递(和使用)表示向量中元素数量的无关变量会在某个地方引入错误。如果您想获得元素的数量,或者只通过向量本身,只需使用std::vector::size()
函数。
此外,您应该通过引用或常量引用来传递类似std::vector
的内容,这取决于传入的向量是否会更改。按值传递std::vector
(正如您现在所做的那样)会导致(不必要的)复制。