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

相关文章

来自专栏量子位

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

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

3395
来自专栏量子位

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

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

3445
来自专栏算法channel

这个例子,妙!

且不论真假,突然觉得倒是很合适用来作为 Hidden Markov Model (HMM) 的例子来讲的,因为和书上课上讲的例子,天气呀遛狗啊还是马克杯啊什么的...

983
来自专栏mathor

细说基姆拉尔森日期公式

 计算给定日期星期几是编程经常会遇到的问题,这里有一个公式: W = (d + 2m + 3(m+1)/5 + y + y/4 - y/100 + y/400...

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

机器学习人工学weekly-2018/8/26

Safety-first AI for autonomous data centre cooling and industrial control

833
来自专栏思影科技

NATURE NEUROSCIENCE:大脑动态隐性状态是行为导向的工作记忆的基础

来自牛津大学的学者Michael J Wolff等人在Nature Neuroscience期刊上发文,提出了一种功能扰动的方法来探测大脑的隐性状态,...

2806
来自专栏大数据文摘

李飞飞计算机视觉成名作:斯坦福CS231n作业详解第二弹!

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

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

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

2898
来自专栏WOLFRAM

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

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

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

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

4618

扫码关注云+社区