2

我正在尝试使用动态编程解决背包问题的变体：

所以我所拥有的是一个具有尺寸的正方形区域：N*N（就像一个棋盘）。在每个方格上，我都有一些值。我能做的是在正方形的值上加一（+1）或删除一（-1）。有一个特殊的规则，如果有相邻的正方形（有共同边的正方形 - 对角线正方形不计算在内）的值等于正方形的新值，则设置所有这些相邻正方形的值归零

目标是尽可能减少所有方格的总值。

例如，如果我有一个 3x3 矩阵，代表一个 3*3 正方形的字段，那么我们可以有这样的东西：

int[3,3] 字段 = { 1, 2, 3,
                   5, 1, 6,
                   7, 3, 9 }

现在，如果我将值为 2 的元素 [0, 1] 减少一个，那么所有元素 [0, 0] [0, 1] 和 [1, 1] 都会将它们的值设置为 0。

所以到目前为止，基本上我所做的就是对每个方格的每个动作以及动作的深度进行评分（这意味着如果一个动作在一个方格上重复多次，我已经计算了评分）并且我将这些评分保存在四个维数组，ratings[action, depth, row, col]。

等级表示平方的总值将减少的数量。

我想要的是找到从字段中删除尽可能多的值的最佳操作顺序。这必须在预定义数量的动作中发生（或者有定义的回合数，我每回合只能做一个动作）。最后一点很明显，我必须从正方形的评级中找出深度子集的哪个组合会给我最高的总评级。

首先，我认为这可以通过子集总和问题来完成，然后通过它们的评级对收到的项目列表进行排序，但之后我意识到这可以通过背包问题来实现，除了评级相互依赖，这里是我的问题来了。例如，如果有一个方块改变了它的值，那么它的相邻方块可能会自动改变它们的评级。我可以写一个方法来检查广场的邻居是否会在行动后改变他们的评级，但这不是让我烦恼的事情。让我担心的是如何通过改变值（正方形的评级）来实现背包问题？

总结一下我到目前为止所拥有的：

  • 我有一个定义的转数（动作）C - 可以表示为矩阵的最大权重
  • 我有每个方块的动作深度（从 1 到 C） - 可以表示为每个项目的权重
  • 我对所有平方（非负整数）都有评级 - 可以表示为项目的值。

对我来说，主要问题是要放入背包的物品的价值可能会根据保留的物品而改变。

我不得不承认我不是从头开始编写我的背包算法，而是我使用了一个已经编写好的算法并根据我的需要对其进行了转换。我从这里得到算法： http: //sriwantha.blogspot.com/2011/07/knapsack-problem-in-c.html

这是我的代码：

//Knapsack problem:

//class for the items in the knapsack
public class Item 
{
    public int row;
    public int col;
    public int action;
    public int depth;
    public int rating;
    public Item(int row, int col, int action, int depth, int rating)
    {
        this.row = row;
        this.col = col;
        this.action = action;
        this.depth = depth;
        this.rating = rating;
    }

    public override string ToString()
    {
        return "row,col,action=" + row + "," + col + "," + action + ", depth=" + depth + ", rating=" + rating;
    }
}

class KnapSackProblem
{
    public static List<Item> FindItemsToPack(List<Item> items, int depthCapacity, out int totalRatingValue)
    {
        int[,] ratings = new int[items.Count + 1, depthCapacity + 1];
        bool[,] keep = new bool[items.Count + 1, depthCapacity + 1];

        for (int i = 1; i <= items.Count; i++)
        {
            Item currentItem = items[i - 1];
            for (int depth = 1; depth <= depthCapacity; depth++)
            {
                if (depth >= currentItem.depth)
                {
                    int remainingDepth = depth - currentItem.depth;
                    int remainingDepthRating = 0;
                    if (remainingDepth > 0)
                    {
                        remainingDepthRating = ratings[i - 1, remainingDepth];
                    }
                    int currentItemTotalRating = currentItem.rating + remainingDepthRating;
                    if (currentItemTotalRating > ratings[i - 1, depth])
                    {
                        keep[i, depth] = true;
                        ratings[i, depth] = currentItemTotalRating;
                    }
                    else
                    {
                        keep[i, depth] = false;
                        ratings[i, depth] = ratings[i - 1, depth];
                    }
                }
            }
        }

        List<Item> itemsToBePacked = new List<Item>();

        int remainDepth = depthCapacity;
        int item = items.Count;
        while (item > 0)
        {
            bool toBePacked = keep[item, remainDepth];
            if (toBePacked)
            {
                itemsToBePacked.Add(items[item - 1]);
                remainDepth = remainDepth - items[item - 1].depth;
            }
            item--;
        }

        totalRatingValue = ratings[items.Count, depthCapacity];
        return itemsToBePacked;
    }
}

从另一种方法我调用背包算法：

List<Item> actionsToDo = new List<Item>();
Item newItemTake;
Item newItemAdd;

for (int depth = 0; depth < maxDepth; depth++)
    {
    for (int row = 0; row < dimension; row++)
    {
        for (int col = 0; col < dimension; col++)
        {
            if (ratings[Take, depth, row, col] >= 0)
            {
                newItemTake = new Item(row, col, Take, depth + 1, ratings[Take, depth, row, col]);
                actionsToDo.Add(newItemTake);
            }
            if (ratings[Add, depth, row, col] >= 0)
            {
                newItemAdd = new Item(row, col, Add, depth + 1, ratings[Add, depth, row, col]);
                actionsToDo.Add(newItemAdd);
            }
        }
    }
}

int totalRating = 0;

List<Item> itemsToBePacked = KnapSackProblem.FindItemsToPack(actionsToDo, maxDepth, out totalRating);

foreach (var item in itemsToBePacked)
{
    Console.WriteLine(item);
}
Console.WriteLine(totalRating);
4

0 回答 0