https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Hardprob%2FMaximum_Weighted_Satisfiability_With_Bound
Hardprob/Maximum Weighted Satisfiability With Bound - История изменений
2026-04-20T02:24:11Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Weighted_Satisfiability_With_Bound&diff=25159&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на <em>\1 ∈ \2</em>
2023-04-17T22:05:30Z
<p>Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на <em>\1 ∈ \2</em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 22:05, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">B∈  </del>N</<del class="diffchange diffchange-inline">m</del>>,  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <<ins class="diffchange diffchange-inline">em</ins>><ins class="diffchange diffchange-inline">B ∈ </ins>N</<ins class="diffchange diffchange-inline">em</ins>>,  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>** для каждой переменной <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">u∈  </del>U</<del class="diffchange diffchange-inline">m</del>>, задан вес <m>w(u)∈  N</m>, такой что <m>B\le\sum\limits_{u∈  U} w(u)≤2\,B</m>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>** для каждой переменной <<ins class="diffchange diffchange-inline">em</ins>><ins class="diffchange diffchange-inline">u ∈ </ins>U</<ins class="diffchange diffchange-inline">em</ins>>, задан вес <m>w(u)∈  N</m>, такой что <m>B\le\sum\limits_{u∈  U} w(u)≤2\,B</m>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** либо <em>B</em>, если <em>F</em> ложно</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** либо <em>B</em>, если <em>F</em> ложно</div></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:25090:newid:25159 -->
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Weighted_Satisfiability_With_Bound&diff=25090&oldid=prev
StasFomin: Массовая правка: замена PCRE \\le\s на ≤
2023-04-17T21:28:04Z
<p>Массовая правка: замена PCRE \\le\s на ≤</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 21:28, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <m>B∈  N</m>,  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <m>B∈  N</m>,  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>** для каждой переменной <m>u∈  U</m>, задан вес <m>w(u)∈  N</m>, такой что <m>B\le\sum\limits_{u∈  U} w(u)<del class="diffchange diffchange-inline">\le 2</del>\,B</m>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>** для каждой переменной <m>u∈  U</m>, задан вес <m>w(u)∈  N</m>, такой что <m>B\le\sum\limits_{u∈  U} w(u)<ins class="diffchange diffchange-inline">≤2</ins>\,B</m>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** либо <em>B</em>, если <em>F</em> ложно</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** либо <em>B</em>, если <em>F</em> ложно</div></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:24962:newid:25090 -->
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Weighted_Satisfiability_With_Bound&diff=24962&oldid=prev
StasFomin: Массовая правка: замена \in на ∈
2023-04-17T18:00:33Z
<p>Массовая правка: замена \in на ∈</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 18:00, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <m><del class="diffchange diffchange-inline">B\in </del>N</m>,  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <m><ins class="diffchange diffchange-inline">B∈  </ins>N</m>,  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>** для каждой переменной <m><del class="diffchange diffchange-inline">u\in </del>U</m>, задан вес <m>w(u)<del class="diffchange diffchange-inline">\in </del>N</m>, такой что <m>B\le\sum\limits_{<del class="diffchange diffchange-inline">u\in </del>U} w(u)\le 2\,B</m>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>** для каждой переменной <m><ins class="diffchange diffchange-inline">u∈  </ins>U</m>, задан вес <m>w(u)<ins class="diffchange diffchange-inline">∈  </ins>N</m>, такой что <m>B\le\sum\limits_{<ins class="diffchange diffchange-inline">u∈  </ins>U} w(u)\le 2\,B</m>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** либо <em>B</em>, если <em>F</em> ложно</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** либо <em>B</em>, если <em>F</em> ложно</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>** либо <m>\displaystyle\sum\limits_{<del class="diffchange diffchange-inline">v\in </del>U'} w(v)</m>, если <em>F</em> истинно.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>** либо <m>\displaystyle\sum\limits_{<ins class="diffchange diffchange-inline">v∈  </ins>U'} w(v)</m>, если <em>F</em> истинно.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать <em>R</em>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать <em>R</em>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:23762:newid:24962 -->
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Weighted_Satisfiability_With_Bound&diff=23762&oldid=prev
StasFomin: Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор булевых переменных <em>U</em>, булевое выражение…»
2023-04-13T17:06:51Z
<p>Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Набор булевых переменных <em>U</em>, булевое выражение…»</p>
<p><b>Новая страница</b></p><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --><br />
* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <m>B\in N</m>, <br />
** для каждой переменной <m>u\in U</m>, задан вес <m>w(u)\in N</m>, такой что <m>B\le\sum\limits_{u\in U} w(u)\le 2\,B</m>.<br />
* Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет <br />
** либо <em>B</em>, если <em>F</em> ложно<br />
** либо <m>\displaystyle\sum\limits_{v\in U'} w(v)</m>, если <em>F</em> истинно.<br />
* Максимизировать <em>R</em>.<br />
<br />
----<br />
{{hard-problem-on-lab17|{{PAGENAME}}}}<br />
<!-- * {{has-testdata-and-visualization}} --><br />
<!-- * {{has-pyomo-model}} --><br />
<!-- * {{has-npc-reduction}} --><br />
<!-- * {{add-random-fuzzing-tests}} --><br />
----<br />
<small><br />
{{ViggoCode|node232}}<br />
<!-- {{GDCode|}} --><br />
<!-- * [ Задача в википедии] --><br />
</small><br />
<!-- end --><br />
<br />
[[Категория:ClassicHardProblems]]</div>
StasFomin