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

相关文章

来自专栏机器学习人工学weekly

机器学习人工学weekly-2018/3/4

1. RL相关 1.1 inverse RL教程,第一部分就是讲Andrew Ng 20年前的奠基论文(我没读原论文,但是惊讶的发现居然全部是用的LP解的)。这...

50280
来自专栏AI科技大本营的专栏

推荐 | 机器学习开源项目 Top 10

编译 | AI科技大本营 一直为开发者提供优质学习资源的Mybridge最近又发布了一篇资源性文章:机器学习领域开源项目Top 10,AI科技大本营做了简要编译...

30780
来自专栏李海辰的专栏

Unity 5.6 光照烘焙系统介绍

Unity 一直致力于解决混合光照的问题,在Unity 5.6 Beta 2版本中加入了不断改进后的功能。本文将为大家分享光照烘焙系统介绍。

3.5K80
来自专栏量子位

DIY发现新行星操作指南 | 谷歌开源了行星发现代码

去年12月,谷歌大脑用机器学习发现了两个系外行星,分别是开普勒80 g和开普勒90 i。 开普勒90 i还是颗类地行星诶! ? △ 因为这次新系外行星的发现,开...

36950
来自专栏IT派

推荐|Kaggle机器学习之模型融合(stacking)心得

此文道出了本人学习Stacking入门级应用的心路历程。 在经过了几天漫长的查询资料和整理,脑子不好,理解顿悟花了不少时间。在学习过程中感谢@贝尔塔的模型融合...

48950
来自专栏WOLFRAM

Mathematica 11 在偏微分方程中的应用

59130
来自专栏深度学习与数据挖掘实战

【AI头条&优质资源】时间序列预测模型:使用深度神经网络RNN+Attention机制

放arxiv那天看了一下,整篇paper思路读下来还是非常清晰的,实验效果也很不错。

50720
来自专栏思影科技

大话脑影像系列之三:趣谈散点图与相关系数

爱因斯坦喊你点击右上角蓝色“思影科技”关注我们 最近不少读者对高大上的机器学习,动态脑网络,曲面形态指标共变网络感到爱不起,针对于此,我们特别推出一...

37960
来自专栏量子位

ACL最佳论文出炉,十四行诗生成、OpenNMT、概率类型学等上榜

李林 编译出品 量子位 报道 | 公众号 QbitAI 今天,2017年度计算语言学协会年会(ACL)评出了5篇最佳…论文,量子位整理介绍如下: 最佳演示论文:...

36450
来自专栏机器学习人工学weekly

机器学习人工学weekly-2018/9/9

Searching toward pareto-optimal device-aware neural architectures

9220

扫码关注云+社区

领取腾讯云代金券