java - Java中的递归动态规划背包解决方案

Question

我编写了这个动态函数来查找背包问题的最大打包值。

static int dyn(int maxItems, int maxSize)
    {
        if(maxItems < 0)
        {
            return 0;
        }
        if(tab[maxItems][maxSize] != -1)
        {

            return tab[maxItems][maxSize];
        }

        if( itemArray[maxItems].s > maxSize)
        {
            result =  dyn(maxItems-1,maxSize);
            return result;
        }
        else
        {
            result =  Math.max(dyn(maxItems-1, maxSize), dyn(maxItems-1, maxSize - itemArray[maxItems].s) + itemArray[maxItems].v);
            tab[maxItems][maxSize] = result;
            return result;
        }

    }

我从 main 调用这个函数

int x = dyn(maxItems - 1, maxSize)

itemArray 结构是

public class Item {
 int v;
 int s;
}

每次我得到的答案都是 0。请告诉我哪里出错了

Answer 1

删除检查 tab[][] != -1 的 if 循环。这永远是正确的，并且它下面的实际背包递归永远不会运行。我假设您用项目填充 itemArray 。现在这应该可以了。

static int dyn(int maxItems, int maxSize)
{
    if(maxItems < 0)
    {
        return 0;
    }

    if( itemArray[maxItems].s > maxSize)
    {
        return dyn(maxItems-1,maxSize);
    }
    else
    {
        int result =  Math.max(dyn(maxItems-1, maxSize), dyn(maxItems-1, maxSize - itemArray[maxItems].s) + itemArray[maxItems].v);
        tab[maxItems][maxSize] = result;
        return result;
    }
}