背包问题算法探究

有N个物品,其价值为数组W[],重量为数组P[],包的承重量为M,问包能承重的最大价值?

一、设F[i,j]为前i个物品放入承重为j的包的最大价值,那必然:

F[i,j] = Max{F[i-1,j],F[i-1,j-P[i]]+W[i]}

可能你会对此公式会有些疑问,为什么会得到此公式,那我们来讲解一下公式,前i个物品放入承重为j的包的最大价值只会存在两种情况:
(1)当不带第i件商品时,那么其最大价值为F[i-1,j]
(2)当带i件商品时,那么前i-1件商品放在剩余重量j-P[i]的最大价值,在加上第i件本身价值,为F[i-1,j-P[i]]+W[i]

二、如何将公式转化为可执行的代码
以下描述的是5个物品,其重量为{2,2,6,5,4},价值为{6,3,5,4,6},承重为10的包的问题

beibao.png

eg:d9的单元格的值是:F[4,9] = Max{F[3,9],F[3,9-5]+4} = Max{c9,c4 + 4} = Max{10,10} = 10
c10单元格的值是:F[3,10] = Max{F[2,10],F[2,10-6]+5} = Max{11,11} = 11

//C为包的承重,N为背包个数,w为物品重量,v为物品价值
    int maxinput(int C,int N ,int w[],int v[])  
    {  
        int[] V = new int[C+1];
        int i,j;   
        for(j=0;j<=C;j++)  
        {  V[j]=0;  
        }  
        for(i=0;i<N;i++)  
        {  
            for(j=C;j>=w[i];j--)  
            {  
                V[j]=max(V[j],V[j-w[i]]+v[i]);  
            }  
        }  
        return(V[C]);  
    }
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容