动态规划法(四)——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 条评论
登录 后参与评论

相关文章

来自专栏mukekeheart的iOS之旅

《JavaScript高级程序设计》学习笔记(2)--JS运算符详解

欢迎关注本人的微信公众号“前端小填填”,专注前端技术的基础和项目开发的学习。 思维导图 前面对JS的运算符的操作很多细节的东西没有提及,今天给大家分享一张网上找...

3434
来自专栏鸿的学习笔记

《推荐系统实践》的阅读笔记

大家新年好!作为新年的第一篇文章,为大家奉上推荐系统的入门书籍《推荐系统实践》的思维导图。对于我而言,因为是全新的领域,囿于能力所限,思维导图可能不是...

703
来自专栏web前端教室

【看录像】~有视频也学不会前端开发。为啥?

视频教程,各种视频教程,教什么的都有,其中自然少不了前端开发。我的所有的课程,都会有对应的录像和源码,那为什么还会有同学搞不定自己的代码呢?

864
来自专栏钱曙光的专栏

为什么有些语言比别的快?

来自Ars Technica的文章评论了影响编程语言速度的各个方面。Ars这个网站虽然自称技术网站,但编程方面的文章一般比较浅,这篇也不例外。虽然文字很长,但无...

1825
来自专栏机器学习算法与Python学习

微视频 | 人工智能会抢走我们的饭碗吗?

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 ?

2868
来自专栏新智元

声音识别的ImageNet诞生,谷歌发布大规模音频数据集

【新智元导读】谷歌今天发布了一个在声音识别上对标图像识别领域中的ImageNet的大型数据库。包含2100万标注视频、5800个小时的音频、527种类型的标注声...

35210
来自专栏应兆康的专栏

2. 如何使用本书来帮助你的团队

在读完本书后,你将会对如何制定机器学习项目中的技术方案有一个深刻的理解。 但是你的队友可能不会理解为什么使用你制定的技术方案,也许你想和你的团队定义一个评估指标...

3549
来自专栏应兆康的专栏

如何使用本书来帮助你的团队

1321
来自专栏镁客网

深入学术研究,物理学家用VR演示弦理论猜想

1184
来自专栏专知

【干货】机器学习知识体系思维导图,一图让你理解所有概念

机器学习 思维导图 / 速查表 思维导图集从数据分析到深度学习来汇总机器学习概念 Overview 机器学习是计算机科学的一个子领域,使计算机不需要明确的编程步...

3709

扫描关注云+社区