C / C ++实现的算法类似于子集总和 [英] C/C++ implementation of an algorithm similar to subset sum

问题描述

问题比背包简单（或一个类型的吧，没有价值，只有正权）。该问题由一个检查数是否也可以是其它的组合。该函数应返回真或假。

The problem is simpler than knapsack (or a type of it, without values and only positive weights). The problem consists of checking whether a number can be a combination of others. The function should return true or false.

例如，

112，并与一个List {17，100，101} 应该返回假， 469 用相同的列表应该返回真， 35 应该返回假， 119 应该返回真等等...

112 and a list with { 17, 100, 101 } should return false, 469 with the same list should return true, 35 should return false, 119 should return true, etc...

编辑：子集和问题会更加精确的比背包

subset sum problem would be more accurate for this than knapsack.

推荐答案

这是观察，这将有助于你的是，如果你的列表是{A，B，C ......}，你要测试的人数为x，则x可被写为仅当x或xa的可写为子列表{B，C，...}的总和的子列表的总和。这让你写一个非常简单的递归算法来解决这个问题。

An observation that will help you is that if your list is {a, b, c...} and the number you want to test is x, then x can be written as a sum of a sublist only if either x or x-a can be written as a sum of the sublist {b, c, ...}. This lets you write a very simple recursive algorithm to solve the problem.

编辑：这里是一些code，考虑到下面的评论。未测试所以大概越野车;并且不一定是最快的。但是，对于一个小的数据集，将完成这项工作整齐。

edit: here is some code, taking into account the comments below. Not tested so probably buggy; and not necessarily the fastest. But for a small dataset it will get the job done neatly.

bool is_subset_sum(int x, std::list::const_iterator start, std::list::const_iterator end)
{
  // for a 1-element list {a} we just need to test a|x
  if (start == end) return (x % *start == 0); 

  // if x is small enough  we don't need to bother testing x - a
  if (x<a) return is_subset_sum (x, start+1, end);

  // the default case. Note that the shortcut properties of || means the process ends as soon as we get a positive.
  return (is_subset_sum (x, start+1, end) || is_subset_sum (x-a, start, end));
}

这篇关于C / C ++实现的算法类似于子集总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！