最优分解问题 c++程序

#include<iostream>

using namespace std

void main(){

int t = 0//输入小于0时退出

int i//当和大于等于t时的数

int sum//和

int final

cin>>t

while(t >0){

if(t <4 ){cout<<t cin>>tcontinue}

i = 2,sum = 0,final = 1

while(sum - t <0){

sum += i

i++

}

int b = sum - t

if(b == 1){

for(int k = 3k <i+1k++){

if(k == i-1) continue

cout<<k<<" "

final*=k

}

}

else for(int k = 2k <ik ++){

if( b == k) continue

cout<<k<<" "

final *= k

}

cout<<"the max number is " <<final <<'\n'

cin>>t

}

}

在vc2005编译的。

最小值是分解的数是最平均的情况下，

相反最不平均的情况下就是最大值了

假设分解为m个数，用a1，a2...am表示

累加【i=1，m】(ai-(n/m))^2，也就是方差越小，结果越大

可以在m=2的时候证明这点，但是m大于2我就证明不了了，但是知道结果就是这样

至于分解的思路

比如n=6，分解成3个数，那么答案就是1,2,3

比如n=16，分解成3个数，答案1,2,13

23分解成4个数，1,2,3,17

就是一开始的数尽可能的小，最后一个数就是剩下的了，这样的方差是最大的，任意此方的和也最大

当然也有无解的，比如6分解成4个数

#include <iostream>

#include <iomanip>

#include <string>

#include <vector>

using namespace std

#define SQRE(a) (a)*(a)

const int infinity=6553

const int exce=-2

const int lineWidth=15

string ori("Do you like those people who always think \

of money and cannot remember the past. ")

//char ori[]="hello world "

//char ori[]="aaa bb ccc "

vector<string>index

int* fun

int** c

int* funChoose

void initial()

{

fun=new int [index.size()+1]

funChoose=new int [index.size()+1]

c=new int* [lineWidth+1]

for (int i=0i<lineWidth+1i++)

{

c[i]=new int [lineWidth+1]

for (int j=0j<lineWidth+1j++)

{

c[i][j]=exce

}

}

for (int i=0i<index.size()+1i++)

{

fun[i]=exce

funChoose[i]=exce

}

}

void debugPrint()

{

cout<<"**************\n"

cout<<"function return:\n"

for(int i=0i<16i++)

{

cout<<setw(5)<<fun[i]<<" "

}

cout<<"\n**************\n"

cout<<"function choose:\n"

for(int i=0i<16i++)

{

cout<<setw(5)<<funChoose[i]<<" "

}

cout<<"\ncost(i,j)"<<endl

for(int i=0i<lineWidthi++)

{

for (int j=0j<lineWidthj++)

{

cout<<setw(5)<<c[i][j]

}

cout<<"\n"

}

}

void split()

{

string tmp=""

for (int i=0i<ori.length()i++)//sizeof 是否有效？

{

if (ori[i]==' ')

{

index.push_back(tmp)

tmp.clear()

}

else

tmp=tmp+ori[i]

}

}

int cost(int i,int j)

{

int val=infinity

int len=0

if (i>j)

{

cerr<<"Error:i>j!"

return exce

}

if (c[i][j]!=exce)

return c[i][j]

else

{

for(int k=ik<jk++)

{

len+=index[k].length()

}

len+=j-i-1//space count

if (len>lineWidth)

{

c[i][j-1]=infinity

return infinity

}

else

{

c[i][j-1]=SQRE(lineWidth-len)

return SQRE(lineWidth-len)

}

}

}

int f(int j)

{

int min=65535

if (fun[j]!=exce)

return fun[j]

else

{

if (cost(0,j)==infinity)

{

for (int k=1k<jk++)

{

if (min>f(k)+cost(k,j))

{

min=f(k)+cost(k,j)

funChoose[j]=k

}

}

}

else

{

min=cost(0,j)

}

fun[j]=min

return min

}

}

void print()

{

vector<int>stack

int size=lineWidth

for (int i=0i<lineWidthi++) //print the line width

{

cout<<"*"

}

cout<<endl

stack.push_back(size)

while(funChoose[size]!=exce)

{

stack.push_back(funChoose[size])

size=funChoose[size]

}

stack.push_back(0)//begin

for (int i=stack.size()i>1i--)//print the plain text

{

for(int j=stack[i-1]j<stack[i-2]j++)

{

cout<<index[j]<<" "

}

cout<<endl

}

}

int main()

{

split()

initial()

cout<<f(index.size())<<endl

print()

return 0

}

采用动态规划的方法完成，至于四步典型过程，着实没有想出来。。。

一般是写惩罚函数、写递归式、完成递归实现，完成从底向上的算法吧

---