分物品演算法

㈠ 關於禮物分配演算法

#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!].