最小背包不会显示正确的结果

Question

我想背包显示最佳解决方案的意义，给定一组具有一定重量和成本的项目，让我们假设它有一个相应的array来保存信息weight[]和cost[]我想要一个背包，显示minimum项目的成本对于给定的重量，它必须填充背包或尽可能接近填充它并显示最佳结果。我编写的代码只显示正确的解决方案，如果背包已填满。我只是想知道它在算法方面有什么问题。

我尝试过修改vanilla Knapsack算法来获得minimum value而不是maximum。

public int MinimumCost(int weight[],int cost[], int n,int W){
    n = cost.length;
    int min_cost[][] = new int[n+1][W+1];

    for (int i = 0; i <= W; i++)
        min_cost[0][i] =999999;

    for (int i = 0; i <= n; i++)
        min_cost[i][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (weight[i-1] > j)
                min_cost[i][j] = min_cost[i-1][j];
            else
                min_cost[i][j] = Math.min(min_cost[i-1][j],min_cost[i-1][j-weight[i-1]]+cost[i-1]);

}


    return min_cost[n][W];
}

我想要最佳解决方案的值，MINIMUM值填充（或尽可能接近填充）给定最大重量的背包。谢谢！

Answer 1

我想如果你没有完全填满你的背包，那么琐碎的最小值总是为0（不带任何物体）。

所以你应该只考虑完全填充背包的问题;否则最小值始终为0，否则问题很难得到解决。

如果W是您可以考虑的最大重量，您可以尝试解决在完全填充尺寸为w的背包时找到最小成本重新分配的问题，其中w为1 ... W。

由您来决定1 ... W中哪个解决方案是您最喜欢的。