动态程序帮助（背包）

Question

我正在研究这个动态规划问题，并且我坚持在 Java

中编写迭代解决方案

目标是找出恰好花费 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;
            }
        }
    }
}

我想我只是没有真正理解迭代步骤的递归关系。

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

它 returns -1 如果不可能恰好花费 X 美分。如果您需要更多信息来理解，请告诉我。尽管我建议对背包问题使用自上而下的方法，因为您不需要为任何单个问题计算所有子问题。

动态程序帮助（背包）

Dynamic Prog Help (knapsack)

java

knapsack-problem

dynamic-programming