r*******g
发帖数: 1335 | 1 每个字符有权重，输入是很多字符，里面可能有重复的，另外一个输入是一个
dictionary，求你用这些字符可以组成的words的最大权重。
我隐约有印象此题在本版讨论过，哪位大侠指点一下？好像还是只有用trie去做？
谢谢了。 |
I******c
发帖数: 163 | 2 我能想到的办法 就是用字典里的词建一个trier.
这个trier其实就是一个多路的树，然后就可以用dfs,每次用输入的字符去试，求出一
个权值最大的path. |
I******c
发帖数: 163 | 3 当然也可以把字典里每个词都单独计算一次。用trier的好处就是如果几个词的前缀相
同的话，重复的计算可以省去。
dfs的时间复杂度是指数级，而题目只是问最大权值，不知道可不可以用dp来做。 |
r*******g
发帖数: 1335 | 4 对，我想到的也是trie，dp做似乎很难，这题有点像backpack实际不是。
【在 I******c 的大作中提到】
: 当然也可以把字典里每个词都单独计算一次。用trier的好处就是如果几个词的前缀相
: 同的话，重复的计算可以省去。
: dfs的时间复杂度是指数级，而题目只是问最大权值，不知道可不可以用dp来做。
|
I******c
发帖数: 163 | 5 backpack是什么算法？
我说的dfs就是backtracking. |
c*****m
发帖数: 271 | 6 不清楚题意，问下：每个字符只能用一次么？一个组成的word的权重是所有组成的字符
权重之和么？最终是要所有组成的words的权重加起来最大么？ |
I******c
发帖数: 163 | 7
我的理解就是看输入。如果输入是aaabb,那么可以用a三次，b两次。如果输入是aab，
那么可以用a两次，b一词
一个组成的word的权重是所有组成的字符
一个词的权重
【在 c*****m 的大作中提到】
: 不清楚题意，问下：每个字符只能用一次么？一个组成的word的权重是所有组成的字符
: 权重之和么？最终是要所有组成的words的权重加起来最大么？
|
r*******g
发帖数: 1335 | 8 word权重就是字符权重之和。
已有的字符不能多用。
【在 c*****m 的大作中提到】
: 不清楚题意，问下：每个字符只能用一次么？一个组成的word的权重是所有组成的字符
: 权重之和么？最终是要所有组成的words的权重加起来最大么？
|
x****y
发帖数: 252 | 9 我也不是很明白这个题意。
word权重怎么由所有组成的字符权重之和？
比如 a权重是50%， b权重也是50%。
如果输入是aaabb,或者输入是aabbb，他们的权重都是250%？应该怎么计算？ |
i*****o
发帖数: 105 | |
s**********1
发帖数: 4651 | 11 亚麻还值得去吗？听说绿卡政策不怎么样，还特别辛苦，最近刚有人跳楼
【在 r*******g 的大作中提到】
: 每个字符有权重，输入是很多字符，里面可能有重复的，另外一个输入是一个
: dictionary，求你用这些字符可以组成的words的最大权重。
: 我隐约有印象此题在本版讨论过，哪位大侠指点一下？好像还是只有用trie去做？
: 谢谢了。
|
h******9
发帖数: 25 | 12 1.重复字符的权重是一样的吗？权重是设定的，不是取决于占输入字符的个数对吗？
2.要是Dict里的字符没有权重，是算不能用还是算权重0？ |
s******n
发帖数: 240 | 13 如果每个字符的weight总是不变的，那么其实一个word的字符顺序是不重要的，对吧？
这样字典就可以简化成set of (字符+出现次数)，然后找输入字符串的字符和次数大于
字典词的最大情况。 |
s*****l
发帖数: 7106 | 14 Same thinking here.
【在 s******n 的大作中提到】
: 如果每个字符的weight总是不变的，那么其实一个word的字符顺序是不重要的，对吧？
: 这样字典就可以简化成set of (字符+出现次数)，然后找输入字符串的字符和次数大于
: 字典词的最大情况。
|
