0%

有 N 种物品和一个容量是 V 的背包。
物品一共有三类:

  1. 第一类物品只能用1次(s<0时)(01背包);
  2. 第二类物品可以用无限次(s=0时)(完全背包);
  3. 第三类物品最多只能用 $s_i$ 次(s>0时)(多重背包);
    每种体积是 $v_i$,价值是 $w_i$。
  • 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
    输出最大价值。
    阅读全文 »

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符
阅读全文 »

给定一个整数矩阵,找出最长递增路径的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。(就是非常经典的滑雪题)

阅读全文 »

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第i件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。

阅读全文 »