`
爱在爪哇
  • 浏览: 7583 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
最近访客 更多访客>>
社区版块
存档分类
最新评论

动态规划之-0-1背包问题

阅读更多
package cn.gao.algorithm2.service;

public class Test7 {

	/**
	 * @param args
	 * 动态规划问题,0-1背包问题
	 * f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值 
	 * f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]} 
	 * 核心思想是:对于第N件物品放或者不放;
	 */
	public static int f(int a[],int b[],int i,int j)/*参数依次为物品重量数组,物品价值数组,物品的数量,剩余背包的重量*/
	{
		if(i==1)
		{
			 if(j>=a[i-1])
			 {
				 return b[i-1];	 
			 }
			 else
			 {
				 return 0;
			 }
		}
	    if(a[i-1]>j)/*第i个物品大于背包重量,直接丢弃*/
	    {
	    	return f(a,b,i-1,j);
	    }
	    else{/*在可选取第i件物品时候,取 选和不选 这二种情况的最大值*/
	    	
	    	return f(a,b,i-1,j-a[i-1])+b[i-1]>f(a,b,i-1,j)?f(a,b,i-1,j-a[i-1])+b[i-1]:f(a,b,i-1,j);
	    }
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
          int a[]={1,3,5,7,9};
          int b[]={8,6,4,2,1};
          int weigth=15;
          System.out.println(f(a,b,a.length,weigth));
	}

}

 

0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics