uva 624 - CD (0-1 knapsack)

http://uva.onlinejudge.org/external/6/624.html

我把这个问题复述一下。输入有很多行,每行都是如下格式

sum n a1 a2 a3 a4

这样的格式。如

5 3 1 3 4

sum = 5 背包的容量是多少

n =3 有多少个物品

1 3 4 每个物品的体积是多少。

然后要你把物品塞进背包里,把这个背包尽可能的塞满。

对于上面的输入,输出是这样:

1 4 sum:5

含义是:体积最多能塞到5。 因为1+4=5。
例如:
10 4 9 8 4 2
对应的输出是:
8 2 sum:10

例如:
20 4 10 5 7 4

对应的输出是:
10 5 4 sum:19
例如:
45 8 4 10 44 43 12 9 8 2
对应的输出是:
4 10 12 9 8 2 sum:45

或者:
43 2 sum:45

也就是说答案并不唯一,但是online judge系统都能接受。

这个问题是经典的动态规划问题,但是我看大多数地方把它归为backtracking。他们是用backtracking and pruning 的方式来解决这个问题。

However,即便是用动态规划解,程序也有很多不同的写法。

有的人是用一个大的矩阵保存计算的中间结果,但是只保存total value,不保存每个物品具体的index。然后最终,backtracking一次这个矩阵,把最大值对应的所有的index计算出来。

而我是在计算的每一步都把index记住,这样我就可以只用两个vector,或者甚至只用一个vector就保存所有的中间值。

struct Result{
  std::vector<size_t> indexes;
  long total;
  Result():total(0){}
  void add(long v,size_t index){
    total+=v;
    indexes.push_back(index);
  }
};

Result resolve(const std::vector& values,long cap){
  if(cap<=0) return Result();
  std::vector* memo=new std::vector;
  memo->resize(cap+1);
  for(size_t j=0;j!=values.size();++j){
      for(long w=1;w<=cap;++w){
        long v=values[j];
        if(w>=v && v+(*memo)[w-v].total > (*memo)[w].total ){
          (*memo)[w]=(*memo)[w-v];
          (*memo)[w].add(v,j);
        }
      }
  }
  Result r=memo->back();
  delete memo;
  return r;
}

它们所说的backtracking,是不是就是自上而下的动态规划呢? (我这个是自下而上的,buttom-up)。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥