文档章节

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

FL_NC
 FL_NC
发布于 2016/08/12 20:11
字数 526
阅读 231
收藏 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
152. Maximum Product Subarray - LeetCode

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

yysue
08/14
0
0
877. Stone Game - LeetCode

Question 877. Stone Game Solution 题目大意: 说有偶数个数字,alex和lee两个人比赛,每次轮流从第一个数字或最后一个数字中拿走一个(偶数个数字,所以他俩拿的数字个数相同),最后比谁拿...

yysue
08/22
0
0
java_面试_01_一个月的面试总结(java)

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

rayner
03/07
0
0
java servic wrapper jvm启动五遍后就停止

STATUS | wrapper | 2013/04/03 12:01:35 | Launching a JVM... INFO | jvm 1 | 2013/04/03 12:01:36 | there are all ok ERROR | wrapper | 2013/04/03 12:01:36 | JVM exited while loadin......

这个世界不真实
2013/04/03
1K
1

没有更多内容

加载失败,请刷新页面

加载更多

Web安全之XSS攻击与防御小结

Web安全之XSS攻防 1. XSS的定义 跨站脚本攻击(Cross Site Scripting),缩写为XSS。恶意攻击者往Web页面里插入恶意Script代码,当用户浏览该页之时,嵌入其中Web里面的Script代码会被执行,从...

前端小攻略
18分钟前
1
0
JavaScript中的继承及实现代码

JS虽然不像是JAVA那种强类型的语言,但也有着与JAVA类型的继承属性,那么JS中的继承是如何实现的呢? 一、构造函数继承 在构造函数中,同样属于两个新创建的函数,也是不相等的 function Fn...

peakedness丶
22分钟前
1
0
记一次面试最常见的10个Redis"刁难"问题

导读:在程序员面试过程中Redis相关的知识是常被问到的话题。作为一名在互联网技术行业打击过成百上千名的资深技术面试官,本文作者总结了面试过程中经常问到的问题。十分值得一读。 Redis在...

小刀爱编程
34分钟前
13
0
TiDB Lab 诞生记 | TiDB Hackathon 优秀项目分享

本文由红凤凰粉凤凰粉红凤凰队的成员主笔,他们的项目 TiDB Lab 在本届 TiDB Hackathon 2018 中获得了二等奖。TiDB Lab 为 TiDB 培训体系增加了一个可以动态观测 TiDB / TiKV / PD 细节的动画...

TiDB
47分钟前
4
0
当区块链遇到零知识证明

本文由云+社区发表 当区块链遇到零知识证明 什么是零知识证明 零知识证明的官方定义是能够在不向验证者任何有用的信息的情况下,使验证者相信某个论断是正确的。这个定义有点抽象,下面笔者举...

腾讯云加社区
56分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部