dynamic-programming - 在 Unbounded Knapsack 算法中选择了哪些项目？

Question

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

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

Answer 1

让我们引入一个新的路径函数，它使用之前计算的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);

}