动态规划算法解决二维背包问题
[ 2011年9月4日 ] 【大 中小】
一个旅行者有一个最多装j公斤，容积k的背包，现在有n种物品，每件的重量分别是w1,b1,w2,b2,w3,b3,......,wn,bn.
每件的价值分别为v1,v2,...,vn.若的每种物品的件数足够多. 求旅行者能获得的最大总价值。
int MaxValue(int n,int j,int *w,int k,int *b,int *v,int ***m)
{
int t = max(w[n],b[n]);
for(int i = 1;i
{
for( int j = 1;j
{
m[n][i][j] = 0;
}
}
for(int i = t;i
{
for(int j = t;j
{
m[n][i][j] = v[n];
}
}
for(int i = n-1;i>1;i--)
{
t = max(w[i],b[i]);
for(int j1 = 1;j1
{
for(int k1 = 1;k1
{
m[i][j1][k1] = m[i+1][j1][k1];
}
}
for(int j1 = t;j1
{
for(int k1 = t;k1
{
m[i][j1][k1] = max(m[i+1][j1][k1],m[i+1][j1-w[i]][k1-b[i]]+v[i]);
}
}
}
m[1][j][k] = m[2][j][k];
if(m[2][j-w[1]][k-b[1]]+v[1]>m[1][j][k])
{
m[1][j][k] = m[2][j-w[1]][k-b[1]]+v[1];
}
return m[1][j][k];
}
【】【告诉好友】【告诉好友】【打印此文】【返回顶部】
免责申明 --------------------------------------------------------------------------------------
以上内容仅代表原创者观点，其内容未经本站证实，中华考试网对以上内容的真实性、完整性不作任何保证或承诺，转载目的在于传递更多信息，由此产生的后果与中华考试网无关；如以上转载内容不慎侵犯了您的权益，请联系我们
，我们将会及时处理。