## DPV 6.19 Solution: Coin change with at most k uses of each coin

Problem Description Solution Subproblem:  For any integers 0 ≤ u ≤ v and 0 ≤ j ≤ k, define T(u, j) to be true if it is possible to make change for u using at most j coins with denominations chosen from x1, x2, . . . , xn. The answer we want is T(v,…

## DPV 6.18 Solution: Coin change with at most 1 use of each coin

Problem Description Solution Subproblem: To make change for u with denominations 1 through i, we have the choice of using a denomination i coin or not. If we use this coin, then we have to make change for u−xi using denominations 1 through i−1. If we don’t use this coin, then we have to make…

## DPV 6.17 Solution: Coins of Denominations (Coin Changes)

Problem Description Solution Subproblem: For any integer 0 ≤ i= ≤ k, define T(i) to denote if it is possible to make change for i using coins of denominations x1, x2, . . . , xn, thus the answer T(v). Recursive formulation: Notice that T(i) is true only if T(i – xi) is true for…

## Prove that High-Degree Independent Set is NP-Complete

Problem In the High-Degree Independent Set (HDIS) problem, you are given a graph G = (V, E) and an integer k, and you want to know whether there exists an independent set V’ in G of size k such that each vertex of V’ is of degree at least k. (For example, the graph in…

## [DPV]8.15 MAXIMUM COMMON SUBGRAPH

Problem Show that the following problem is NP-complete.MAXIMUM COMMON SUBGRAPH Solution First, we need to prove that MAXIMUM COMMON SUBGRAPH (MCSP) is in the class NP. For given solution V1′ and V2′ , we simply remove these sets of vertices and their incident edges from G1 and G2 and check where the left G1′ and…

## [DPV]8.2 Search versus decision.

Language 中文版请访问：https://huadonghu.com/archives/cn/dpv8-2-search-versus-decision/ Problem Description Search versus decision. Suppose you have a procedure which runs in polynomial time and tells you whether or not a graph has a Rudrata path. Show that you can use it to develop a polynomial time algorithm for RUDRATA PATH (which returns the actual path, if it exists). Solution Let Ad…

## [Leetcode] 969. Pancake Sorting 烙饼排序

Solution Code 聊一聊NP-Hard

## [DPV]8.3 STINGY SAT

Language For English Version, please visit: https://huadonghu.com/archives/en/algorithms/dpv8-3-stingy-sat-2/ Problem Description STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY SAT is NP-complete. STINGY SAT 是：对于对于一组cluses和一个正整数k，…