java - 动态编程帮助(背包)

Question

我正在解决这个动态编程问题，并且我一直坚持用 Java 编写迭代解决方案

目标是找到花费 X 美分所需的最少卡路里数。如果我们不能恰好花费 X 美分，那么就没有解决方案。我们给定了 N 个元素，每个元素都有值(value) 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;
            }
        }
    }
}

我想我只是不太理解迭代步骤的递归关系。

Answer 1

无论您是自上而下还是自下而上编程，递归关系都是相同的。既然您看过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。如果您需要更多的理解信息，请告诉我。尽管我建议对背包问题使用自上而下的方法，因为您不需要计算任何单个问题的所有子问题。