01背包问题

题目:有A(2kg,6$);B(2kg,3$);C(6kg,5$);D(5kg,4$);E(4kg,6$)五种物品各一件,括号内标示该物品的重量和价值,假设你有一个容量为10kg的背包来装上述物品,试求出可以装下的最大价值。

分析:若装了c物品后达到了最大价值

-------------------当前最大价值 =(背包总重量-c物品重量)时的最大价值+c物品的价值----------------


每件物品的考虑方式:

    1st:该物品重量是否大于背包总重量,大于则无法装入背包;

    2nd:若能装入背包:

        v1=当前最大价值 =(背包总重量-该物品重量)时的最大价值+c物品的价值

       v2=不装该物品时背包最大价值

        选v1和v2中较大者。



物品重量数组:w[6]={0,2,2,6,5,4}     //增加数组长度便与代码编写,

物品价值数组:v[6]={0,6,3,5,4,6}    //增加数组长度便与代码编写,

动态规划二维辅助数组:dp[6][11]   //增加数组长度便与代码编写,并将第一行,列初始为0

---------------------dp[i][j]表示在前i个物品中用容量为j的背包可以装入的最大价值-------------------

状态转移方程:

------------------------------------dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}-----------------------------------



核心代码:

for(j=0;j<10;j++)

    for(i=1;i<5;i++)

    { 

        if(w[i]>j)  dp[i][j]=dp[i-1][j];

            else 

            {

            int v1=dp[i-i][j-w[i]]+v[i];

            int v2=dp[i-1][j];

            if(v1>v2) dp[i][j]=v1;

                else 

                {

                dp[i][j]=v2;

                }

            }

    }

}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容