文档章节

01背包问题 动态规划 java实现

FL_NC
 FL_NC
发布于 2016/08/12 20:11
字数 526
阅读 179
收藏 0
点赞 0
评论 0

日常吐槽,日常打代码,理论可以去看其他博客,只贴出代码,代码有注释

public static int Knapsack(int v[],int w[],int c,int n,int m[][])
      {
	   int jMax=Min(w[n]-1,c);//自底向上,若最后一个物体的重量小于背包的总容量,取最后一个物体的重量为界限
	                          //小于w[n]都放不不了
	   for(int j=0;j<=jMax;j++)m[n][j]=0;//背包容量小于最后一个物品的重量,不能放入该物品
	   for(int j=w[n];j<=c;j++) m[n][j]=v[n];//大于w[n]能放入
	   int i;
	   for(i=n-1;i>0;i--){//从n-1到1
	    jMax=Min(w[i]-1,c);
	    for(int j=0;j<=jMax;j++){//背包容量j小于物体w[i],则不能放入
	    	m[i][j]=m[i+1][j];
	    }
	    for(int j=w[i];j<=c;j++) {
	    	m[i][j]=Max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//大于则尝试放入,与不放入相比,区总价值大的
	    }
	   }
	   m[0][c]=m[1][c];//此时m[1][c],m[2][c],m[3][c]......m[n-1][c],m[n][c]的最优值已算出来
	   if(c>=w[0]){
		  m[0][c]=Max(m[i+1][c],m[i+1][c-w[1]]+v[0]);//此时i等于0
	   }
	 return m[0][c];
	}
 //输出选取物体的下标,从0开始
public static void Tracback(int v[],int w[],int c,int n,int m[][]){
	int x[] = new int[5];
	for(int i=0;i<n;i++){
		if(m[i][c]==m[i+1][c]){//相等则该物体不屈
			x[i]=0;
		}else{
			c=c-w[i];//取该物体后背包容量建w[i]
			x[i]=1;
		}	
	}
	if(m[n][c]>w[n]) {//只剩最后一个一物体,若背包容量能装下,则一定取
		x[n]=1;
	}else{
		x[n]=0;
	}
	for(int i=0;i<x.length;i++){
		System.out.println(x[i]);
	}
}
  public static	int Max(int a,int b){
	  if(a>=b){
	    return a;
	  }else{
	    return b;
	  }
	}
  public static 	int Min(int a,int b){
	  if(a<b){
	    return a;
	  }else{
	    return b;
	  }
	}

代码测试

//测试函数
    @org.junit.Test
	public void Test1(){
    	//背包容量
    	   int c=10;
    	   //物体个数
    	    int n=4;
    	    //物品质量
    	    int w[]={2,2,6,5,4};
    	    //物品价值
    	    int v[]={6,3,5,4,6};
    		  int m[][] =new int[200][200];
    	//    int m[][] ={};
    	System.out.println(ZeroOne.Knapsack(v,w,c,n,m));
    	ZeroOne.Tracback(v,w,c,n,m);
		
	}

 

© 著作权归作者所有

共有 人打赏支持
FL_NC
粉丝 7
博文 7
码字总数 5117
作品 0
哈尔滨
程序员
怎样衡量两个字符串的相似度(编辑距离动态规划求解)

前言 目前计算句子相似性有很多不同的方案,比如基于语义词典的方法、基于相同词汇的方法、基于统计的方法和基于编辑距离的方法。这篇文章先介绍编辑距离的基础。 编辑距离 编辑距离其实就是...

超人汪小建 ⋅ 06/12 ⋅ 0

白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下! 这是...

木子昭 ⋅ 01/31 ⋅ 0

面试必看!2018年4月份阿里最新的java程序员面试题目

目录 技术一面(23问) 技术二面(3大块) 性能优化(21点) 项目实战(34块) JAVA方向技术考察点(15点) JAVA开发技术面试中可能问到的问题(17问) 阿里技术面试1 1.Java IO流的层次结构...

美的让人心动 ⋅ 04/16 ⋅ 0

Java基础|Java特性与HelloWorld运行流程

【Java基础】 Java语言特点:(着重了解两个)开源、跨平台。 跨平台如何实现:通过JVM实现,JVM充当Java和不同OS之间的翻译器,不同OS对应不同JVM。 Java语言的平台:JavaSE、JavaME(Androi...

darlingwood2013 ⋅ 05/29 ⋅ 0

阿里巴巴菜鸟Java一面11个问题,你会几个呢?

近日,w3cschool app开发者头条上分享了阿里菜鸟Java程序员一些面试题。 这吸引了不少程序员小伙伴们的注意。 在分享阿里菜鸟Java程序员面经前,来看下Java面试一些面试经验分享: 0、Java高...

W3Cschool ⋅ 04/03 ⋅ 0

Multi-Host Connections(三)

ReplicationDriver 针对Master/Slave,Mysql jdbc drivrer : ReplicationDriver https://dev.mysql.com/doc/connector-j/8.0/en/connector-j-master-slave-replication-connection.html http......

墨子Zhai ⋅ 06/06 ⋅ 0

菜鸟网络java岗面经 已拿offer

牛客网上看了很多面经现在回馈一下牛友。 我是一个双非二本java。首先要谢谢我的一个李姓同学。他先去蚂蚁金服。这才告诉我们,双非二本只要技术好大公司也是不会拒绝你的。 还有就是牛客网上...

牛客网 ⋅ 05/10 ⋅ 0

关于 Java IO(二):从面向字节到面向字符

在上一篇文章中,我们以面向字节的输入为例,介绍了 Java 中 IO 的结构。在这篇文章中,主要介绍面向字节的输入输出是怎么转换到面向字符的输入输出的。 面向字符的输入输出指的是输入输出的...

Happioo ⋅ 04/09 ⋅ 0

升级到JDK9的一个BUG,你了解吗

概述 前几天在一个群里看到一个朋友发了一个demo,说是JDK的bug,昨天在JVM的一个群里又有朋友发了,觉得挺有意思,分享给大家,希望大家升级JDK的版本的时候注意下是否存在这样的代码,如果...

你假笨 ⋅ 06/06 ⋅ 0

Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区 ⋅ 05/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Nginx服务架构初探(四):nginx服务器的rewrite功能

nginx服务器的rewrite功能 1.nginx后端服务器组的配置 1>upstream name {…} name是给服务器组限的组名 2>server address [parameters]; address为服务器地址 parame......

余温灬未存 ⋅ 今天 ⋅ 0

layer.prompt使文本框为空的情况下也能点击确定

最近一直在使用layui,但是用到弹出层layer.prompt时,如果文本框是空的话点击确定没有反应,不能向下执行。 但是我又需要空值,看看我原来的代码。 123456789 layer.prompt...

孟飞阳 ⋅ 今天 ⋅ 0

Linux普通文件压缩工具gzip、Bzip2、xz

第六章 文件压缩和打包 6.1 压缩打包介绍 Linux环境常见压缩文件类型: .zip,.gz,.bz2,.xz, .tar.gz,.tar.bz2,.tar.xz 压缩打包的目的 方便文件传输 节省磁盘空间 减少传输花费的时间 ...

弓正 ⋅ 今天 ⋅ 0

移动弹窗基础知识浅析——IOS弹窗体系

摘要: 最为常见的【弹窗】反而是最“捉摸不定”的东西。各种类型的弹窗傻傻分不清楚,不知道在什么场景下应该用哪种弹窗。尤其是遇到“二次确认”等场景…… 因此,打算从头整理移动弹窗的基...

阿里云云栖社区 ⋅ 今天 ⋅ 0

zabbix短信报警统计以及报表展示

一、需求 由于我们的业务报警比较频繁,之前是针对每个报警进行具体处理,但是有时还会重复出现,或者后续处理有时忘记跟进等,因此进行报警短信的统计,可以针对一些问题与业务跟进,明确后...

o翡翠谷o ⋅ 今天 ⋅ 0

JNI 输出LOG

1、导入log头文件。在你使用的 .c/ .cpp 文件中,导入 log.h 头文件。 #include<android/log.h> 2、在android.mk 加上 LOCAL_LDLIBS := -llog 或 LOCAL_SHARED_LIBRARIES := liblog 3、定义L......

国仔饼 ⋅ 今天 ⋅ 0

主线程pthread_exit 作用

#include <iostream>#include <pthread.h>#include <unistd.h>using namespace std;#define NUM_THREADS 10void* say_hello(void* args){ int i = *((int*)args);/......

xxdd ⋅ 今天 ⋅ 0

崛起于Springboot2.X之Mybatis-xml方式操作mysql数据库(3)

序言:当第一篇讲道Mybatis的时候,只要使用过mybatis的java程序员100%都会知道这种方式,因为这是最广泛最全面的编写sql操作mysql数据库的方式,高级sql的编写往往通过xml方式,接下来进入正...

木九天 ⋅ 今天 ⋅ 1

移动弹窗基础知识浅析——IOS弹窗体系

摘要: 最为常见的【弹窗】反而是最“捉摸不定”的东西。各种类型的弹窗傻傻分不清楚,不知道在什么场景下应该用哪种弹窗。尤其是遇到“二次确认”等场景…… 因此,打算从头整理移动弹窗的基...

猫耳m ⋅ 今天 ⋅ 0

spring elasticsearch 2.4 date 日期

1.mappingPUT user_behavior { "mappings": { "user_behavior": { "properties": { "date": { "type": "createDate", ......

xiaomin0322 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部