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

相关文章

来自专栏跟着阿笨一起玩NET

使用延迟的FileSystemWatcher来避免重复触发事件

  程序里需要监视某个目录下的文件变化情况: 一旦目录中出现新文件或者旧的文件被覆盖,程序需要读取文件内容并进行处理;但在实际处理中发现当一个文件产生变化时,C...

912
来自专栏xingoo, 一个梦想做发明家的程序员

【插件开发】—— 6 SWT 复杂控件使用以及布局

前文回顾: 1 插件学习篇 2 简单的建立插件工程以及模型文件分析 3 利用扩展点,开发透视图 4 SWT编程须知 5 SWT简单控件的使用与布局搭...

2349
来自专栏木宛城主

曾今的代码系列——自己的分页控件+存储过程实现分页

项目里面的测试代码,仅供参考 LoginByAjax <title>Ajax登陆</title> <script src="Scripts/c...

1865
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

983
来自专栏我和未来有约会

Silverlight制作逐帧动画 v2 - part2

Silverlight制作逐帧动画 v2 - part2 在这里完善了一下算法,加入了fps的机制进去。 private string[] ...

1896
来自专栏张善友的专栏

弹出式模态窗体选择文本控件

2006年就要到来了,最近比较忙,很少更新blog,今天发一个模态窗体选择文本控件辞旧迎新.新年在发几个asp.net2.0 webPart控件同各位分享: ...

1907
来自专栏c#开发者

xmldocument内嵌入另一个xmldocument,xmlnode的方法

string xmlstr1 = @"<root><head>myHead</head><body></body></root>"; s...

2725
来自专栏大内老A

开发自己的Data Access Application Block[下篇]

上接:[原创] 我的ORM: 开发自己的Data Access Application Block - Part I 4. Database 下面来介绍重中之重...

2246
来自专栏james大数据架构

CSS好看的按钮

好看的按钮 <style> .btn { BORDER-RIGHT: #7b9ebd 1px solid; PADDING-RIGHT: 2px; BORDE...

2017
来自专栏互联网开发者交流社区

STC-单片机控制系统

1113

扫码关注云+社区