poj 1010 解题心得

March 16, 2013 21:33


上周吧,看到1010题时,思路有些乱,想了一会后没理清,然后这周有那么一两天下班弄了一两小时, 一看到这题又开始头大,就一直没管了。鉴于这周末太无聊,下午一觉醒来,外面居然下雨了,于是, 吃完我的晚餐泡面就着手解决此题。

和同事说过这题,让我叫背包问题,搜一下,恩,真的看不懂,还有什么NP问题,呃,真心不懂, 看不出个样来就自己理思路了。。。

首先要知道最佳答案,我就要知道所有的答案,用个递归把有的结果组合起来, 然后再慢慢来比较找出最佳结果。

我用了个递归,首先传入客户的需求值,也就是用户要购买邮票的价值,第二个参数限制了递归的深度, 这里就是结果中的第几张邮票, 第三个参数是我定义的一个结果类,里面可以存储4张邮票, 及对邮票数量统计,比较都在这个类里,最后一个参数就是从给出的第几张邮票开始循环结果, 防止不必要的计算

StampsGroup best_result(int value, int lack, StampsGroup result, int index = 0) {
  int tmp_result_count = result.count;
  int compare_result;
  StampsGroup best, tmp_sg;

  for (int i = index; i < types_count; i++) {
    result[MAX_SELL_STAMPS - lack] = i;
    result.count = tmp_result_count + types[i];

    if (result.count > value) { continue; }

    if (result.count < value && lack > 1) {
      tmp_sg = best_result(value, lack - 1, result, i);
    } else {
      tmp_sg = result;
    }

    if (tmp_sg.count == value) {
      compare_result = tmp_sg.compare(best);

      if (compare_result == 0) {
        best.result_count += 1;
      } else if (compare_result > 0) {
        best = tmp_sg;
        best.result_type = compare_result;
      }
    }
  }

  return best;
}

在计算最佳结果前我把输入的邮票排序了,虽然例子给的是排序好的,不过给出的是不是排序好的没说明。。

然后是邮票的比较,StampsGroup的一个实例方法,首先比较不同邮票的数量, 我这里存放的是邮票在排序好的结果中的索引。数量相同再比较最大的那张, 还相同就比较最小的那张

int compare(const StampsGroup & sg) {
  int tc = types_count(), sgtc = sg.types_count();

  if (tc < sgtc) {
    return -1;
  } else if (tc == sgtc) {
    if (max_used_index < 0) { return 0; }
    if (stamps[max_used_index] > sg.stamps[sg.max_used_index]) {
      return 11;
    } else if (stamps[max_used_index] < sg.stamps[sg.max_used_index]) {
      return -11;
    } else {
      if (stamps[0] < sg.stamps[0]) {
        return 21;
      } else if (stamps[0] > sg.stamps[0]) {
        return -21;
      }
    }
    return 0;
  } else {
    return 1;
  }
}

最后说一下输入,开始我也没想到,看了别人的心得我才加上去的,就是输入相同的邮票就只记4张, 写到这我发现我判断相同的邮票,居然有个前提是输入的邮票是排序好的。呃,我也懒的改了,反正过了。 而且内存256K,时间0MS,嘿嘿

void add_type(int stamp) {
  if (last_type != stamp) {
    last_type = stamp;
    last_type_count = 1;
  } else {
    last_type_count += 1;
    if (last_type_count > MAX_SELL_STAMPS) { return; }
  }

  types[types_count++] = stamp;
}

下面是源代码,为了贴出来,我又加上了一些注释。。。

#include <iostream>
#include <algorithm>

using std::cout; using std::cin; using std::endl;

#define MAX_TYPES 25
#define MAX_SELL_STAMPS 4

// 存放4张邮票在这里
class StampsGroup {
public:
  // 初始为-1表示没存放邮票
  StampsGroup(){
    count = 0;
    result_count = 1;
    result_type = 0;
    max_used_index = -1;
    for (int i = 0; i < MAX_SELL_STAMPS; i++) {
      stamps[i] = -1;
    }
  }

  StampsGroup(const StampsGroup & sg) {
    *this = sg;
  }

  StampsGroup & operator=(const StampsGroup & sg) {
    for (int i = 0; i < MAX_SELL_STAMPS; i++) {
      stamps[i] = sg.stamps[i];
    }
    count = sg.count;
    result_count = sg.result_count;
    result_type = sg.result_type;
    max_used_index = sg.max_used_index;

    return *this;
  }

  // 为了方便取stamps。。。
  int & operator[](const int i) {
    if (i > max_used_index) { max_used_index = i; }
    return stamps[i];
  }

  // 邮票的比较,本来是重载<的,后来思想凌乱为了返回是比较到哪里就返回了int。。。。
  int compare(const StampsGroup & sg) {
    int tc = types_count(), sgtc = sg.types_count();

    if (tc < sgtc) {
      return -1;
    } else if (tc == sgtc) {
      if (max_used_index < 0) { return 0; }
      if (stamps[max_used_index] > sg.stamps[sg.max_used_index]) {
        return 11;
      } else if (stamps[max_used_index] < sg.stamps[sg.max_used_index]) {
        return -11;
      } else {
        if (stamps[0] < sg.stamps[0]) {
          return 21;
        } else if (stamps[0] > sg.stamps[0]) {
          return -21;
        }
      }
      return 0;
    } else {
      return 1;
    }
  }


  // 计算一共有多少种类型,主要是排除相同的
  int types_count() const {
    int tmp = 4;

    if (stamps[0] < 0) { return 0; }

    for (int i = MAX_SELL_STAMPS - 1; i > 0; i--) {
      if (stamps[i] < 0) {
        tmp -= 1;
        continue;
      } else if (stamps[i] == stamps[i - 1]) {
        tmp -= 1;
      }
    }

    return tmp;
  }


  int count;
  int result_count;
  int result_type;
  int max_used_index;

private:
  int stamps[MAX_SELL_STAMPS];
};



// 这个类的实例主要是用来输入邮票和计算结果
class Stamps {
public:
  Stamps(){
    reset();
  }


  // 增加一种邮票,就这个大于4张的不再输入,前提是排序好的,呃懒的改了
  void add_type(int stamp){
    if (last_type != stamp) {
      last_type = stamp;
      last_type_count = 1;
    } else {
      last_type_count += 1;
      if (last_type_count > MAX_SELL_STAMPS) { return; }
    }

    types[types_count++] = stamp;
  }


  // 完成了输入,在这里排序一下。。。
  void completed_input() {
    std::sort(types, types + types_count);
  }


  // 计算最佳选择
  void customer_best(int value) {
    cout<<value;

    StampsGroup sg = best_result(value, MAX_SELL_STAMPS, StampsGroup());

    if (sg.count != value) {
      cout<<" ---- none\n";
    } else {
      cout<<" ("<<sg.types_count()<<"): ";

      show_stamps_group(sg);
    }
  }


  // 这个递归就是计算用的
  StampsGroup best_result(int value, int lack, StampsGroup result, int index = 0) {
    int tmp_result_count = result.count;
    int compare_result;
    StampsGroup best, tmp_sg;

    for (int i = index; i < types_count; i++) {
      result[MAX_SELL_STAMPS - lack] = i;
      result.count = tmp_result_count + types[i];

      if (result.count > value) { continue; }

      if (result.count < value && lack > 1) {
        tmp_sg = best_result(value, lack - 1, result, i);
      } else {
        tmp_sg = result;
      }

      if (tmp_sg.count == value) {
        compare_result = tmp_sg.compare(best);

        if (compare_result == 0) {
          best.result_count += 1;
        } else if (compare_result > 0) {
          best = tmp_sg;
          best.result_type = compare_result;
        }
      }
    }

    return best;
  }



  // 把这个实例重置,用来接收新的邮票数据
  void reset() {
    types_count = 0;
    last_type = -1;
    last_type_count = 0;
  }


private:
  int types[MAX_TYPES];
  int types_count;

  int last_type;
  int last_type_count;


  // 显示结果
  void show_stamps_group(StampsGroup & sg) {
    if (sg.result_count > 1) {
      cout<<"tie\n";
      return ;
    }

    for (int i = 0; i < MAX_SELL_STAMPS; i++) {
      if (sg[i] < 0) { break; }
      cout<<types[sg[i]]<<" ";
    }
    cout<<endl;
  }
};


int main() {
  Stamps stamps;
  int tmp;

  while (cin>>tmp) {
    // 输入所有邮票
    while (tmp) {
      stamps.add_type(tmp);
      cin>>tmp;
    }

    // 完成输入了
    stamps.completed_input();

    // 接收输入的客户,然后输出结果
    while (cin>>tmp && tmp) { stamps.customer_best(tmp); }

    // 完成了,重围邮票计算对象
    stamps.reset();
  }

  return 0;
}

Comments: