g*****n
发帖数: 21 | 1 There's a book and each sentence consists of several words. How to find the
minimal set of words which can used by the reader to understand half of
total number of the sentences. Each sentence is readable if the reader know
all the words.
I can only think of brute force solution -- do word counting on every
possible collection of half number of sentences and choose the minimal. But
that's exponential C(n,n/2).
Any better solution?
Thanks |
J*****n
发帖数: 4859 | 2 回溯法对这类题目是万能的。不过认为有更好的算法。 |
m*******r
发帖数: 98 | 3
the
know
But
Simple greedy strategies do not work here.
Sounds like a NPC problem.
If it is NPC, then the brute force method is fine.
【在 g*****n 的大作中提到】
: There's a book and each sentence consists of several words. How to find the
: minimal set of words which can used by the reader to understand half of
: total number of the sentences. Each sentence is readable if the reader know
: all the words.
: I can only think of brute force solution -- do word counting on every
: possible collection of half number of sentences and choose the minimal. But
: that's exponential C(n,n/2).
: Any better solution?
: Thanks
|
a****y
发帖数: 99 | 4 for me, it looks like a NP problme
IMHO, a greedy solution:
a mixed-integer program
minimize z= sum_{i} I_{word i} # I_{word i} is binary , 1 included,
otherwise 0 .
subject to sum_{each sentence} exp{ (total word # - sum_I_{word i} ) * c
}>= # of sentence/ 2
the constanc c can to be adjusted to depressed unreadable sentence.
an improvement : assume I_{word i} can be a real number among [0, 1] ,
reduce the MIP to a LP. solve it, take the max I_{word i} to be 1 and fix it
. then do it until find a feasible solution.
the
know
But
【在 g*****n 的大作中提到】
: There's a book and each sentence consists of several words. How to find the
: minimal set of words which can used by the reader to understand half of
: total number of the sentences. Each sentence is readable if the reader know
: all the words.
: I can only think of brute force solution -- do word counting on every
: possible collection of half number of sentences and choose the minimal. But
: that's exponential C(n,n/2).
: Any better solution?
: Thanks
|
l******e
发帖数: 470 | 5 set cover problem. an NPC problem.
greedy works fine here.
the
know
But
【在 g*****n 的大作中提到】
: There's a book and each sentence consists of several words. How to find the
: minimal set of words which can used by the reader to understand half of
: total number of the sentences. Each sentence is readable if the reader know
: all the words.
: I can only think of brute force solution -- do word counting on every
: possible collection of half number of sentences and choose the minimal. But
: that's exponential C(n,n/2).
: Any better solution?
: Thanks
|
u******s
发帖数: 157 | 6 What does NPC mean? Thx. |
