2

動的計画法を使用して、ナップザック問題のバリエーションを解決しようとしています。

だから私が持っているのは、次元を持つ正方形のフィールドです：N * N（チェス盤のような）。各正方形には、いくつかの値があります。私にできることは、正方形の値に 1 (+1) を追加するか、1 を削除 (-1) することです。正方形の新しい値と等しい値を持つ隣接する正方形 (共通の辺を持つ正方形 - 対角線の正方形は数えない) がある場合、そのようなすべての隣接する正方形の値が設定されるという特別な規則があります。ゼロに

目標は、すべての正方形の合計値をできるだけ減らすことです。

たとえば、3*3 の正方形のフィールドを表す行列 3x3 がある場合、次のようなものを作成できます。

int[3,3] フィールド = { 1, 2, 3,
                   5、1、6、
                   7、3、9}

ここで、値が 2 の要素 [0, 1] を 1 減らすと、すべての要素 [0, 0] [0, 1] と [1, 1] の値が 0 に設定されます。

したがって、基本的に私が今まで行ってきたことは、各アクションを各正方形のアクションの深さで評価することです (つまり、1 つのアクションが 1 つの正方形で数回繰り返された場合の評価を計算しました)。これらの評価を 4 で保持します。次元配列、ratings[action, depth, row, col].

評価は、正方形の合計値が減少する数を表します。

私が望むのは、フィールドから可能な限り多くの値を削除する最適な一連のアクションを見つけることです。そして、これは事前定義された数のアクションで発生する必要があります (または、定義された数のターンがあり、各ターンに 1 つのアクションしか実行できません)。そして最後に述べたように、正方形の評価から深さのサブセットのどの組み合わせが最高の合計評価を与えるかを見つけなければならないことは明らかです。

最初に、これはサブセット合計の問題で実行できると考え、その後、受け取ったアイテムのリストを評価で並べ替えましたが、その後、評価が互いに依存していることを除いて、ナップザックの問題でこれを実現できることに気付きました。私の問題がどこに来るのか。たとえば、その値を変更する正方形がある場合、隣接する正方形の評価が自動的に変更される可能性があります。アクション後に広場の隣人の評価が変わるかどうかを確認する方法を書くことはできますが、これは私を悩ませているものではありません。私が心配しているのは、値 (正方形の評価) を変更してナップザック問題をどのように実現するかということです。

私がこれまでに持っているものを要約すると：

  • 定義されたターン数 (アクション) 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