【01与完全】背包解析

发布时间:2016-12-11 6:33:12 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【01与完全】背包解析",主要涉及到【01与完全】背包解析方面的内容,对于【01与完全】背包解析感兴趣的同学可以参考一下。

想来这个月就要结束了,我也是玩耍了这么久,终于也要开始继续更新练习了。 受到了亲人的极大地鼓舞,我要做好最后的冲刺工作才行。努力把不懂不会的知识,给巩固了。 前面两种类型的背包磨叽了这么久,总算有眉目了。 /* 修正下述代码的分析。 01背包,与完全背包都可以使用一维数组解决。 使用一维数组解决的时候, 01背包的j,列属性,背包当前的容量,从0...V。 完全背包的j,列属性,背包当前的容量,从V...0。 使用二维数组的时候,没有这个问题。 二维数组时, 01背包如此比较:f[i][j] = max{f[i-1][j], f[i-1][j-w[i]] + v[i]} 完全背包如此比较:f[i][j] = max{f[i][j], f[i][j-w[i]] + v[i]}      注意后者的f[i]与f[i-1] 修正日期:2014-2-21 */ 背包问题中比较核心的代码: 下面的是01背包的问题。 for(i=1;i<=n;i++)// i代表只考虑前i个小时的情况 { scanf("%d%d",&wi,&hpi); for(j=hpi;j<=hp;j++)// j表示在前i个小时还有j点hp时 { if ( f[i-1][j]>f[i-1][j-hp]+wi )\\ 比较是吃还是不吃是最优 { f[i][j]=f[i-1][j];\\ 不吃的时候体重不变 } else { f[i][j]=f[i-1][j-hpi]+wi;\\ 吃的时候体重下降 } //f[i][j] = max( f[i-1][j], f[i-1][j-hpi]+wi); } } 下面是完全背包 for(i=1;i<=n;i++)// i代表只考虑前i个小时的情况 { scanf("%d%d",&wi,&hpi); for(j=hpi;j<=hp;j++)// j表示在前i个小时还有j点hp时 { f[i][j] = max( f[i-1][j], f[i][j-hpi]+wi); //f[j] = max( f[j], [j-hpi]+wi); }} //关键点在这里f[i-1][j-hpi] 或者f[i][j-hpi] //是看上面一行的最优数据,还是本行的最优数据, //即是本i行的数据,还是i-1行的数据。 //使用f[i][j-hpi],比较本行的数据,属于完全背包,每个物品可以选择多次 //使用f[i-1][j-hpi],比较上一行的数据,属于01背包,每个物品只可以选择一次。 //对于完全背包,可以处理成一维数组进行比较

上一篇:一道面试题统计胜负数的
下一篇:linux日常应用管理(3)---syslog中央日志服务器

相关文章

相关评论