分物品算法

㈠ 关于礼物分配算法

#include<iostream>
using namespace std;

int main()
{
cout << "请输入n"<<endl;
int n;
cin>>n;
int *pn=new int[n];//输入礼物个数
float *pValue = new float[n]; //礼物价值
float *pValue1 = new float[n];//第一个人的礼物价值
float *pValue2 = new float[n];//第二个人的礼物价值
cout << "输入价值" <<endl;
for (int i = 0; i < n ; i ++) //将所有的值存起来
{
cin >> pValue[i];
}
int row1 = 0;
int row2 = 0;
float fvalue1 = 0;
float fvalue2 = 0;
for (int j = 0; j < n ; j ++)
{
if (fvalue1 <= fvalue2)
{
pValue1[row1] = pValue[j];
fvalue1 += pValue1[row1];
row1 ++;
}
else
{
pValue2[row2] = pValue[j];
fvalue2 += pValue2[row2];
row2 ++;
}
}
cout <<"第一个"<< fvalue1 << endl;
cout <<"第二个"<< fvalue2 << endl;

delete[] pn;
delete[] pValue;
delete[] pValue1;
delete[] pValue2;
pn = NULL;
pValue = NULL;
pValue1 = NULL;
pValue2 = NULL;

return 0;
}

㈡ 贪心算法几个经典例子

[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于本例题中的3种贪心策略，都无法成立，即无法被证明。

㈢ 序号为1至n的n个人,分序号为1至n的n个物品,序号不重合的概率,的算法

回答：
这个问题是一个经典问题,即“乱序问题”.
n个人分n个物品,不管序号重不重,共有n!种分法；
序号不重的分法共有d(n) = n!∑{i=0,n}[(-1)!/i!].
故序号不重的概率P(n)是
P(n) = d(n)/n!= ∑{i=0,n}[(-1)!/i!].