動態PROG幫助（揹包）

我工作的這個動態規劃問題，我卡在Java中動態PROG幫助（揹包）

的目標是要找到的熱量最低數量才能準確地度過寫迭代求解X美分。如果我們不能花費X美分，那麼就沒有解決方案。我們給出N個物品的數量，每個物品的價值V和卡路里C歸因於它。

public static void iterative(int[] v, int[] c, String[] items, int X, int num_items) 
{ 
    System.out.println("Iterative"); 

    int N = num_items; 
    int[] min = new int[X]; 


    int i, j; 
    for(i=1 i < X; i++) { 
     min[i] = Integer.MAX_VALUE; 
    } 

    min[0] = 0; 
    for(i=1;i<=X;i++) 
    { 
     for(j=0;j<N;j++) 
     { 
      if(v[j]<=i && ((min[i-v[j]]+c[i]) < min[i])) //Wrong? 
      { 
       min[i] = min[i-v[j]] + 1; 
      } 
     } 
    } 
}

我想我只是不真正瞭解迭代步驟的遞歸關係。

來源

2015-05-29 Leroy

你是否清楚揹包算法。？ – Saif

對我來說還是很新鮮的東西，只是看着http://en.wikipedia.org/wiki/Knapsack_problem和其他例子。 – Leroy

重複關係將是相同的，不管你是自上而下還是自下而上編程。既然你已經看過http://en.wikipedia.org/wiki/Knapsack_problem重現關係將保持不變。只有變化是，在揹包問題中，您會得到一個限制（重量限制），並且您應該最大化該限制中的值。但既然你想花費X美分，你需要特別檢查它。我知道這是java語言特定的問題，但我寫了一個C++代碼。 Java轉換應該非常簡單，我希望這有助於。

#define INTMAX 1000000 
int solve(int *v,int *c,int X,int n){ 
    int **result= new int * [n]; 
    for(int i=0;i<n;i++){ 
     result[i]=new int[X+1]; 
    } 
    //initialization with the first object. INTMAX shows it's not possible to find items in exactly X cents. 
    for(int i=1;i<=X;i++){ 
     if(v[0]==i) 
      result[0][i]=c[0]; 
     else 
      result[0][i]=INTMAX; 
    } 
    for(int i=1;i<n;i++){ 
     for(int j=1;j<=X;j++){ 
      // either you can choose ith object or leave it. Check explicitly for the case when you can't select items with X cents. 
      result[i][j]=min((j>=v[i])?(c[i]+result[i-1][j-v[i]]):INTMAX, result[i-1][j]); 
      cout<<"i:"<<i<<"\tj:"<<j<<"\tresult:"<<result[i][j]<<"\n"; 
     } 
    } 
    return result[n-1][X]==INTMAX?-1:result[n-1][X]; 
}

如果它不可能花費X分錢，它將返回-1。讓我知道你是否需要更多的理解。雖然我會建議使用自頂向下的方法來解決揹包問題，因爲您不需要計算任何單個問題的所有子問題。

來源

2015-05-29 21:16:29 Naman

謝謝@Naman我不太瞭解C，但是我儘可能地把它放在一起。 – Leroy

@Leroy沒問題，我很久沒有Java了，否則我肯定會把它放在Java中。但我想這個概念應該清楚。如果不是，請讓我知道，我很樂意提供幫助。 – Naman

動態PROG幫助（揹包）

回答

相關問題