标签: knapsack-problem

我的作业有问题。我一直在搜索 stackoverflow 和其他网站，看看我正在处理哪种问题，结果我不确定这是背包问题还是垃圾箱包装问题。这是问题所在：

一位老太太买了N件产品，每件产品的重量（kg）不同，她想把所有的东西都装进一个能装K公斤的袋子里。找出权重之和尽可能接近 K 的对象集。

我正在编写具有多个约束的背包 0-1 的变体。除了重量约束之外，我还有数量约束，但在本例中，我想解决背包问题，因为我的背包中需要恰好有 n 件物品，且重量小于或等于 W。目前正在为简单的 0-1 案例实现一个动态编程 ruby​​ 解决方案，基于http://rosettacode.org/wiki/Knapsack_problem/0-1#Ruby上 Rosetta Code 的代码。

实施固定数量限制的最佳方式是什么？

如果给你一组具有值和重量的项目:[(w1,v2),(w2,v2),...(wn,vn)],以及两个容量相等的背包Knap1和Knap2,目标是确定可以分别进入Knap1和Knap2的项目S1和S2的最佳子集是什么,并最大化背包的值和容量.

解决这个问题的一种不正确的方法是首先使用所有项目作为候选项的DP编程算法填充Knap1,然后使用Knap1中的剩余项目填充Knap2.

我不明白为什么如果两个背包具有相同的容量,这个算法是不正确的.有人可以解释或举例吗？

我在R中创建了这个简单的代码来解决带有递归功能的Knapsack程序

n <- c(0,1,2,3,4)
v <- c(10,40,30,50)
w <- c(5,4,6,3)
k <- 10


myfunction  <- function(n,k){
  if (n==0 | k==0){
  output <- 0
  } else if (w[i] > k) {
        output <- myfunction[i-1,w]
  } else {
        output <- max(v[i]+ myfunction(i-1, k-w[i]),myfunction(i-1,k))
      }
return(myfunction)
}

但是,我没有得到一个值作为输出,而是整个函数.例如,如果我输入:myfunction(4,10)

我没有得到90的值,但整个功能输出.

这些是价值观

我正在开发一款游戏,我发现了一个问题,我必须解决这个问题来处理一个类似于包装问题的组件布局.

总结一下我需要做的事情,假设我有一个类似于下面的空间:

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

其中每个角单元为4x4,而中心单元为3x3(因此其余角单元为3x4和4x3).然后我有一组元素放在这些块中,可以从1x1到3x3不等(我认为还不需要任何4x4,但它不应该改变任何东西).当然,这些元素不能跨越线条,必须完全位于一个块内.

哪个可能是分配它们的最佳方式？如果没有必要,我宁愿不让它们全部粘在一起(例如,如果周围有足够的空间将它们分开,则不要将两个元素放在一起).我正在寻找一个简单的算法,也因为情况非常有限..

奖金问题:假设除了这9个(可能是其他3-4个)之外的其他区块我怎么能比新的区块优先考虑这些区块？(我的意思是在达到填充阈值之前不使用附加块)

当然我正在寻找一般的想法,没有实现:)

是否有任何贪婪算法可以为非分数（0-1 背包）背包问题提供最佳解决方案？我知道有一个小数版本的 Knapsack 给出了最佳解决方案。

我当地的火车服务最近添加了一个透析通勤选项.我正在尝试确定在给定日期找到给定一组往返旅行的最便宜的票组合的算法.

这是英文问题.给定一天和每天的骑行,以下哪种组合最便宜.

• 往返机票,每次往返费用为w.
• 7天连续7天的门票,费用为x,无限次乘坐.
• 在连续30个日历日内无限次乘坐的30天票价y.
• 成本为z的 365天机票,可在365个连续日历日内无限次乘坐.

由于我很乐意将此限制为一次仅解决一年,我认为日期列表可以很容易地存储在看起来像这样的数组中.

{0,0,1,1,1,0,0,2,1,0,0,0,4,0,1,1,...,0,1,1,5}

数量等于每天往返次数.

我可以使用什么算法来确定涵盖所有行程的最便宜的票组合？

我想知道幂集问题能否转化为背包问题？在我看来，它们是相同的，例如，我们可以将其视为幂集，即每个递归阶段都会启动 2 个递归调用（一个采用 thi元素，另一个绕过它）。我也可以像背包问题一样用动态规划来解决它，所以这让我想知道是否所有幂集问题都可以转化为背包问题。那是对的吗 ？

以下是硬币变化的代码片段，其中一个具有 O(2 ^N ) 时间复杂度，另一个具有 O(N ² ) 运行时间的动态编程。

// O(2^N) time complexity
void bruteforce(int[] coins, int i, int N, String expr) 
{
     if (i == coins.length) {
         if (N == 0)
            count++;
         return;
     }

     if (N >= coins[i])
         recursion(coins, i, N - coins[i], expr + " " + coins[i]);
     recursion(coins, i + 1, N, expr);
}

// O(N^2) time complexity
int dynamicProgramming(int[] coins, int N) 
{
     int [] dp = new int[N …

据我所知，背包问题使用动态规划来根据每个项目的前一项找到它的最佳解决方案。该假设假设解决方案取决于项目的顺序。为什么最终的解决方案不取决于顺序？

这是背包算法还是装箱算法？我找不到确切的解决方案，但基本上我有一个固定的矩形区域，我想用完美的正方形填充它，这些正方形代表我的物品，其中每个物品都有不同的重量，这会影响它们相对于其他物品的大小。

它们将从左上到右下从大到小排序。

另外，即使我需要完美的正方形，最终也允许一些非均匀缩放填充整个空间，只要它们仍然保留其相对面积，并且非均匀缩放是用尽可能少的量完成的。

我可以使用什么算法来实现这一目标？