无界背包算法中选择了哪些物品？

Question

无界背包算法中选择了哪些物品？

3

我正在使用一维数组来获取最终答案，但我也需要获取选定的项目。如何实现？

    private static int UnboundedKnapsack(int capacity, int n, int[] itemValue, int[] itemWeight)
    {
        int[] dp = new int[capacity + 1];

        for (int i = 0; i <= capacity; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (itemWeight[j] <= i)
                {
                    dp[i] = Math.Max(dp[i], dp[i - itemWeight[j]] + itemValue[j]);
                }
            }

        }
        return dp[capacity];
    }

- Sam

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Muhimin_Osim · Accepted Answer

我们来介绍一个新的路径（path）函数，使用之前计算出来的dp数组可以得到最优的物品选择。

private static void path(int capacity, int n, int[] itemValue, int[] itemWeight, int[] dp){
    if(capacity == 0) return; // here you handle when the function will end. I assume capacity should be empty at the last
    int ans = 0, chosenItem;
    for(int j = 0; j < n; j++){
        int newAns = dp[capacity - itemWeight[j]] + itemValue[j];
        if(newAns > ans){
            ans = newAns;
            chosenItem = j;
        }
    }
    printf("%d ",chosenItem); // here you get the current item you need to select;

    path(capacity - itemWeight[chosenItem], n, itemValue, itemWeight, dp);

}