动态规划之-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));}}

?