文档章节

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

FL_NC
 FL_NC
发布于 2016/08/12 20:11
字数 526
阅读 191
收藏 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
哈尔滨
程序员
白话版 动态规划法

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

木子昭
01/31
0
0
java_面试_01_一个月的面试总结(java)

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM内存调优(了解是怎么回事,一般做项...

rayner
03/07
0
0
152. Maximum Product Subarray - LeetCode

Question 152. Maximum Product Subarray Solution 题目大意:求数列中连续子序列的最大连乘积 思路:动态规划实现,现在动态规划理解的还不透,照着公式往上套的,这个问题要注意正负,需要...

yysue
今天
0
0
怎样衡量两个字符串的相似度(编辑距离动态规划求解)

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

超人汪小建
06/12
0
0
android无framework Java应用开发

在android下,其实有另外的一类应用程序,他们用Java开发,但却不使用android的应用框架,不包含android应用程序四大组件中的任何一个,几乎就与我们平常在PC机上开发的那些Java应用程序一样...

WolfCS
2013/12/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Nexus Repository Manager 搭建私有docker仓库

Nexus Repository Manager 搭建私有docker仓库 2018年05月08日 14:44:23 阅读数:115 1.下载nexus3的镜像: docker pull sonatype/nexus3 2.使用镜像启动一个容器: docker run -d --name n...

linjin200
5分钟前
0
0
大数据技术的发展趋势

大数据领域已经涌现出了大量新的技术,它们成为大数据采集、存储、处理和呈现的有力武器。这些技术下一步将如何发展?它们之中哪些技术 将广为流行?又会诞生哪些新的技术? 技术趋向多样化,...

董黎明
7分钟前
1
0
谷歌浏览器插件入门示例

实现:任何网址实现图片下载和获取当前域名的cookies的json字符串。 图片下载是给小白用的,可以选中批量下载,获取cookies 是为了方便程序员调试用。 获取cookies: git地址: https://gite...

NLGBZJ
9分钟前
2
0
152. Maximum Product Subarray - LeetCode

Question 152. Maximum Product Subarray Solution 题目大意:求数列中连续子序列的最大连乘积 思路:动态规划实现,现在动态规划理解的还不透,照着公式往上套的,这个问题要注意正负,需要...

yysue
10分钟前
0
0
IDEA工具 jdk,tomcat,maven 配置

设置JDK、tomcat、maven的版本 一、JDK      如果下拉列表没有,SDKS ---> + ----> 选择下载的JDK目录 ---> APPLY OK    二、tomcat 三、Maven    四、生成 git 本地创库...

君千殇520
10分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部