关于礼物分配算法

来源:百度知道 编辑:UC知道 时间:2024/05/31 23:15:14
题目:父亲给两兄弟分配N个礼物礼物,礼物的价值分别为N1,N2,N3……Nn,为了让两兄弟高兴,父亲决定让两人得到的礼物总价值差的绝对值最小,尽量让分配结果公平,请用动态规划算法为父亲写出礼物分配的算法。

#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;
cou