电脑软硬件应用网
当前位置: 电脑软硬件应用网 > 设计学院 > 网络编程 > C语言 > 正文
动态规划算法解决二维背包问题
动态规划算法解决二维背包问题
2010-2-26 9:03:00  文/xiaobao   出处:电脑软硬件应用网   

    一个旅行者有一个最多装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<t;i++)
    {
        for( int j = 1;j<t;j++ )
        {
            m[n][i][j] = 0;
        }
    }

    for(int i = t;i<w[n];i++)
    {
        for(int j = t;j<b[n];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<t;j1++)
        {
            for(int k1 = 1;k1<t;k1++)
            {
                m[i][j1][k1] = m[i+1][j1][k1];
            }
        }

        for(int j1 = t;j1<=j;j1++)
        {
            for(int k1 = t;k1<=k;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];
    }

  • 上一篇文章:

  • 下一篇文章:
  • 最新热点 最新推荐 相关文章
    用C语言实现的闹钟程序
    C#实现Windows关机的代码
    用动态规划法求组和数的算法
    循环结构程序具有哪3个组成部分?
    const成员函数有什么特点?
    c语言求平均分程序
    一道关于指针的C语言题
    C语言求3个整数的最大公约数
    BM模式匹配算法C语言实现
    从键盘输入任意5个4位整数存入数组a…
    关于45IT | About 45IT | 联系方式 | 版权声明 | 网站导航 |

    Copyright © 2003-2011 45IT. All Rights Reserved 浙ICP备09049068号