动态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帮助（背包）

回答

相关问题