请问这种算法在背包的变化工作？ [英] Will this algorithm for a variation on the knapsack work?

问题描述

我不知道有多少变化，它实际上是，但这里的问题是：

您即将开始了一次漫长的旅程，你这样做之前，你需要收拾你的包。你有选择的N个项目，你可以随身携带。每个项目都有一个重量和价值重估presenting如何用这将是。您将不能携带超过于K公斤。什么是你可以采取与项目的最高总价值？ （你只能有每个项目的一个副本。）

我已经创建了一个算法，我认为将解决使用DP的问题，但我不知道这是否会工作，这将是巨大的，如果你一会就来看看它。 注意：它更像是伪code和算法的组合，我也不太清楚如何可以写的

假设k是最大重量。  两个数组：一个包含每个项目瓦特[]，而另一个值v []

的重量。

 对于i = 0; I＆LT; numberOfItems;我++
 {
    值= 0
    K = MaxWeight;
    为（J =; J＆LT; numberOfItems; J ++
    {
        如果（J =ⅰ）
        {
            如果（K  - 瓦特[I]≥= 0）
            {
                K = K-W [i]于
                值=价值+ V [I]
            }
        }
        其他
        {
            如果（K  -  W [J]＆GT; = 0）
            {
                K = K-W [J]。
                值=价值+ V [J]。
            }
        }
    }
}
 

解决方案

没有，你贪婪的算法是行不通的。

检查这个例子：

  MaxWeight = 12
项目= 4 5 4 4（每个价值1）
 

您算法会选择项目1和2（或项目2和3，或3和4）。最佳的解决办法是采取项1，3和4。

I am not sure how much of variation it actually is, but here is the problem:

You are about to set out on a long journey, before you do so you need to pack your bag. You have a selection of N items which you could take along. Each item has a weight and value representing how useful it will be. You will not be able to carry more than than K kilograms. What is the maximum total value of the items you can take with? (You can only have one copy of each item.)

I have created an algorithm that I think will solve the problem using DP, but I am not sure if it will work, it would be great if one of you would take a look at it. Note: it is more like a combination of psuedo code and a algorithm, I am not too sure how to write either.

Assuming k is the max weight. Two arrays: one containing the weight of each item w[] and the other the value v[].

 for i = 0; i<numberOfItems; i++
 {
    value = 0
    k = MaxWeight;
    for(j = i; j<numberOfItems; j++
    {
        if(j = i)
        {
            if(k - w[i] >= 0)
            {
                k = k-w[i]
                value = value + v[i]
            }
        }
        else
        {
            if(k - w[j] >= 0)
            {
                k = k-w[j]
                value = value + v[j]
            }
        }
    }
}

解决方案

No, your greedy algorithm won't work.

Check this example:

MaxWeight = 12
Items = 4 5 4 4 (each value is 1)

Your algorithm would choose items 1 and 2 (or items 2 and 3, or 3 and 4). Optimal solution is to take items 1, 3 and 4.

这篇关于请问这种算法在背包的变化工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！