向量点乘最小值

两个n维的向量，向量的点乘是指将向量对应维度的乘积相加，但是我们可以将向量维度交换下可以得到更小的向量点乘，例如3维向量：【1, 3, ?5】和【4, ?2, ?1】，最小向量点乘为-27，即将维度变为：[3,1,-5]和[-2,-1,4]，程序设计要求：输入一个整数n为向量的维度，然后输入两个n维度的向量，用空格区别向量元素，输出为一行，包含一个整数，为最小的点乘。

我写的代码为：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int fun(int*,int*,const int);
void main()
{
	cout<<"please enter the dimension of the vetor: ";
	int n;
	cin>>n;
	cout<<"the first vector: ";
	int *x=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>x[i];
	}
	cout<<"the second vector:";
	int *y=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>y[i];
	}

	cout<<fun(x,y,n);

}

int fun(int* A,int *B,const int n)
{
	int temp=0,temp1=0,index=0;
	vector<int> vec;
	for(int i=0;i<n;i++)
	{
		vec.push_back(i);
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<n;i++)
	{
		temp1+=A[i]*B[i];
	}
	while(next_permutation(vec.begin(),vec.end()))
	{
		for(int i=0;i<n;i++)
		{
			index=vec[i];
			temp+=A[index]*B[i];
		}
		if(temp<temp1) temp1=temp;
		temp=0;
	}
	return temp1;
}

当然也可以直接对其中一个向量的元素进行全排列，然后计算出对应的点积，返回最小值：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int fun(int*,int*,const int);
inline void res(int *H,int n);
inline int fac(int x);
void main()
{
	cout<<"please enter the dimension of the vetor: ";
	int n;
	cin>>n;
	cout<<"the first vector: ";
	int *x=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>x[i];
	}
	cout<<"the second vector:";
	int *y=new int[n];
	for(int i=0;i<n;i++)
	{
		cin>>y[i];
	}

	cout<<fun(x,y,n);

}

int fun(int* A,int *B,const int n)
{
	int temp=0,temp1=0,index=0;
	for(int i=0;i<n;i++)
	{
		temp1+=A[i]*B[i];
	}
	sort(A,A+n);
	vector<int> vec;
	while(next_permutation(A,A+n))
	{
		for(int i=0;i<n;i++)
		{
			temp+=A[i]*B[i];
		}
		if(temp<temp1)
		{
			temp1=temp;
			vec.clear();
			vec.insert(vec.begin(),A,A+n);
		}
		temp=0;
	}
	for(vector<int>::iterator ite=vec.begin();ite<vec.end();ite++)
		cout<<*ite<<'\t';
	cout<<endl;
	return temp1;
}

向量点乘最小值,布布扣,bubuko.com

向量点乘最小值

原文：http://blog.csdn.net/daida2008/article/details/29409013