动态规划法(四)——0/1背包问题

问题描述

有n个物体,重量分别是w0~wn-1,每个物体放入背包后可获得的收益分别为p0~pn-1,背包载重为M,且所有物体要么放要么不放,不能只放一部分。求如何放物体可以得到最高的收益。

问题分析

设f(i,m)表示第i步背包的总收益,其中i表示当前进行到了第i步,m为当前背包载重,则当前第i步只有两种选择:

  1. 将第i个物体放入背包 此时背包总收益就变成f(i-1,m-wi)+wi。
  2. 第i个物体不放入背包 此时背包总收益就是f(i-1,m)。

第i步究竟怎么选择,知道就取决于这两种选择那个结果更大。因此要分别计算者两种情况的值,选较大者作为第i步的结果。 这就是一个典型x的递归。

代码实现

// 表示每一个物体是否放入背包
boolean[] isAdd = new boolean[n];
// 存储每个物体的重量
int[] weight = new int[n];
// 存储每个物体的收益
int[] p = new int[n];

/**
 * 0/1背包问题的递归函数
 * @param i : 当前是第几步
 * @param m : 当前背包载重
 * @return 最大收益
 */
int knap( int i, int m ){
    if ( i==-1 ) return 0;
    if ( weight[i]>m )
        return knap( i-1, m );

    int a = knap(i-1,m);
    int b = knap(i-1,m-weight[i])+p[i];
    if ( a>b )
        return a;
    else{
        isAdd[i] = true;
        return b;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT技术精选文摘

使用深度学习预测员工流失率

1683
来自专栏量子位

仅用18天,英伟达新型GAN合成真假难辨高清明星脸

安妮 编译整理 量子位 出品 | 公众号 QbitAI 考眼力:你能分出下面哪张图是电脑合成的吗? 是这位神似年轻时莱昂纳多的神秘男子—— ? 还是这位卷发碧瞳...

2583
来自专栏大数据挖掘DT机器学习

R语言学习路线和常用数据挖掘包

对于初学R语言的人,最常见的方式是:遇到不会的地方,就跑到论坛上吼一嗓子,然后欣然or悲伤的离去,一直到遇到下一个问题再回来。当然,这不是最好的学习...

3126
来自专栏量子位

有记忆会推理的可微分神经计算机,DeepMind现在开源了代码

王新民 编译自 GitHub 量子位 报道 | 公众号 QbitAI ? 去年10月,Google旗下DeepMind在《Nature》上发布第三篇论文,宣布搞...

3386
来自专栏思影科技

渐进型多发硬化症(PPMS)相关的rich-club失连

来自INIMS的Jan-Patrick Stellmann等人在neurology期刊上发表了一篇关于MS的结构脑网络研究,研究主要探寻了病人结构脑网络连接的组...

3247
来自专栏PPV课数据科学社区

【学习】趣味数据挖掘——借水浒传故事,释决策树思路

决策树(又称判定树,DecisionTree)是硕、博士生数据挖掘课程要点和难点,教学实践表明,这一章需要数学基础知识多,难得有趣。明知是难点,偏向难点行,再难...

3234
来自专栏牛客网

算法工程师:非科班机器学习工程师养成计划虐心面试实录一点人生经验

这是一篇不太专业的算法工程师面经,希望能给非科班想要从事机器学习工作的同学或学弟学妹一些建议,同时也回馈给予我很大帮助的牛客网。目前拿到的offer有:网易、三...

6386
来自专栏思影科技

EEG和fNIRS同步研究揭示年龄和神经反馈对运动想象信号的影响

注释:这篇文章相当长,请耐心看完。 来自德国奥尔登堡大学心理学部的Catharina Zich等人在Neurobiology of Aging杂志上发表了一项基...

3376
来自专栏专知

Kaggle比赛实战教程

【导读】在Kaggle比赛中,作者将尝试纽约出租车持续时间预测的挑战。他将使用 Pandas、matplotlib 和 xgost 的组合作为 python 库...

1260
来自专栏码洞

水塘抽样与阶层固化

简单抽样算法就是从固定的n个元素里随机选出k个元素,这样每个元素被选的概率都是平等的k/n。简单抽样是最简单的抽样算法,同样也是使用最为普遍的算法。

692

扫码关注云+社区