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));
}
}