帮忙看看程序,关于背包问题动态划分法
高人能否提供个函数如何进行动态划分
#include <stdio.h> ;

const int MAX_KNAPSACK_NUM 100 //最大物品数

struct WidgetInfo
{ int m_nID; //物品ID
float m_fVolume; //重量
float m_fValue; //价值
float m_fDensityOfValue; //单位价值
}widget[MAX_KNAPSACK_NUM];

//得到物品数量，包容积和物品信息
int GetWidgetInfo(int* nWidgetNumber, float* fBagVolume);

int main()
{
int nWidgetNumber = 0; //物品数量
float fBagVolume = 0.0; //包容积
float fBagValue = 0.0; //包内总价值

if(GetWidgetInfo(&nWidgetNumber,&fBagVolume)==0)//输入信息
return 0;
//使用动态规划如何得到最优结果并打印???
//主要目的就是输出包里能装物品的最大价值情况下的物品ID
}

int GetWidgetInfo(int* nWidgetNumber,float* fBagVolume)
{
int nNumber = 0; //物品数量
float fVolume = 0.0; //包容积
float fAllWidgetsValue = 0.0; //包内总价值
float fAllWidgetsVolume= 0.0; //所有物品容积

printf( "input total number of widgets: "); //输入总数量
scanf( "%d ",&nNumber);
if (nNumber==0) return 0;
if(nNumber> MAX_KNAPSACK_NUM) //物品数量太多

{
return 0;
}
*nWidgetNumber = nNumber;

printf( "input total volume of bag: "); //输入包容积
scanf( "%f ",&fVolume);
if (fVolume==0.0) return 0;
*fBagVolume = fVolume;

for(i=1;i <=nWidgetNumber;i++) //输入每件物品的信息
{
printf( "Input ID= %d volume of widget= ",i); //重量
scanf( "%f ",&widget[i].m_fVolume);
fAllWidgetsVolume=fAllWidgetsVolume+ widget[i].m_fVolume;
if (widget[i].m_fVolume==0)
return 0;
printf( "Input i= %d value of widget=: ",i); //价值
scanf( "%f ",&widget[i].m_fValue);
if (widget[i].m_fValue==0) return 0;
widget[i].m_nID=i; //ID
widget[i].m_fDensityOfValue=widget[i].m_fValue / widget[i].m_fVolume; //单位价值
}
if(fAllWidgetsVolume <=fBagVolume) //物品总容积小于包容积
{
printf( "Volume of all widgets <= Volume of bag!\n ");
return 1;
}
return 1;
}

[解决办法]
int F(int i, int y)

{// 返回f ( i , y ) .

if (i == n) return (y < w[n]) ? 0 : p[n];

if (y < w[i]) return F(i+1,y);

return max(F(i+1,y), F(i+1,y-w[i]) + p[i]);

}