Showing np complete for subset sum variation

The subset sum problem is where you are given a set of integers $ S={x1,x2,…,xn}$ and you want to find a subset $ S′⊆S$ such that its sum equals some k. I already know this problem is NP complete and I’ve seen the proof for it using 3-SAT.

However, what if there was an added condition that we would return YES if the entire set was made up of the same integer? So we return yes if some subset equals $ k$ OR if the set has all the same numbers.

I know this is NP, but I’m struggling to choose which problem to reduce from to show NP completeness.

My question is, what problem should I try to reduce from to make this as easy as possible? I’ve been stuck on this for hours…

Can’t create Variation label for SharePoint site collection

Good day,

I have some problem with creating multi-language SharePoint site. I have site collection with “SharePoint Server Publishing Infrastructure enabled”. I follow this article here.

Following the article (Create the source variation site) I go to Site Collection Administration, click Variation labels. On the Variations Label page, I click New Label. I try to select Location field Value.

In the article was written “It they will be at the top level of the site collection, just type a forward slash (/)”

I type “/” in the Location field and get the error “The root site of the options should be the publication site”. I can’t understand, what is wrong if “SharePoint Server Publishing Infrastructure” option is enabled. “SharePoint Server Publishing” is enabled too.

Thank you in advance.

Principal variation search: how to keep track of the best move

I have a Java implementation of the Principal Variation Search algorithm, and it looks like that:

public final class PrincipalVariationSearchGameEngine          <S extends AbstractState<S, P>,          P extends Enum<P>>             extends AbstractGameEngine<S, P> {      public PrincipalVariationSearchGameEngine(             EvaluatorFunction<S> evaluatorFunction,             int depth) {         super(evaluatorFunction, depth, Integer.MAX_VALUE);     }      @Override     public S makePly(S state,                       P minimizingPlayer,                       P maximizingPlayer,                       P initialPlayer) {         state.setDepth(depth);          return makePlyImplTopmost(state,                                   depth,                                   Double.NEGATIVE_INFINITY,                                   Double.POSITIVE_INFINITY,                                   initialPlayer == minimizingPlayer ? -1 : 1);     }      /**      * Performs the search directly under the root node denoted by       * {@code state].      *       * @param state the root state of the game tree to search.      * @param depth the total depth of the search.      * @param alpha the alpha cutoff value.      * @param beta  the beta cutoff value.      * @param color the color. -1 for minimizing player, +1 for maximizing      *              player.      * @return the game board after optimal move from {@code state}.      */     private S makePlyImplTopmost(S state,                                  int depth,                                  double alpha,                                  double beta,                                  int color) {         boolean firstChild = true;         S bestState = null;         double tentativeScore = color == -1 ?                                 Double.POSITIVE_INFINITY :                                 Double.NEGATIVE_INFINITY;          for (S child : state.children()) {             double score;              if (firstChild) {                 firstChild = false;                 score = -makePlyImpl(child,                                       depth - 1,                                       -beta,                                       -alpha,                                      -color);                 bestState = child;                 tentativeScore = score;             } else {                 score = -makePlyImpl(child,                                       depth - 1,                                       -alpha - 1.0,                                       -alpha,                                      -color);                  if (color == -1) {                     if (tentativeScore > score) {                         tentativeScore = score;                         bestState = child;                     }                 } else {                     if (tentativeScore < score) {                         tentativeScore = score;                         bestState = child;                     }                 }                  if (alpha < score && score < beta) {                     score = -makePlyImpl(child,                                           depth - 1,                                          -beta,                                          -score,                                          -color);                      if (color == -1) {                         if (tentativeScore > score) {                             tentativeScore = score;                             bestState = child;                         }                     } else {                         if (tentativeScore < score) {                             tentativeScore = score;                             bestState = child;                         }                     }                 }             }              if (alpha < score) {                 alpha = score;             }              if (alpha >= beta) {                 break;             }         }          return bestState;     }      private double makePlyImpl(S state,                                int depth,                                double alpha,                                double beta,                                int color) {         if (state.getDepth() == 0                  || state.checkVictory() != null                 || state.isTerminal()) {             return color * evaluatorFunction.evaluate(state);         }          boolean firstChild = true;          for (S child : state.children()) {             double score;              if (firstChild) {                 firstChild = false;                 score = -makePlyImpl(child,                                       depth - 1,                                       -beta,                                       -alpha,                                      -color);             } else {                 score = -makePlyImpl(child,                                       depth - 1,                                       -alpha - 1.0,                                       -alpha,                                      -color);                  if (alpha < score && score < beta) {                     score = -makePlyImpl(child,                                           depth - 1,                                          -beta,                                          -score,                                          -color);                 }             }              alpha = Math.max(alpha, score);              if (alpha >= beta) {                 break;             }         }          return alpha;     } } 

This, however, does not work since it returns suboptimal (next) moves. I believe that the culprit is this if statement:

if (color == -1) {     if (tentativeScore > score) {         tentativeScore = score;         bestState = child;     } } else {     if (tentativeScore < score) {         tentativeScore = score;         bestState = child;     } } 

How to gray out options in dropdown when certain variation is choosen instead of dissappearing

I am looking for a way to gray out the options in the dropdown of a woocommerce product page. Currently i have 520 variations for a product. Example below.

Here is the link to the product page:

So essentially it works as needed, however i wanted to know if there is a way to still show all the options for each dropdown, which would be grayed out, and the available options for a particular variation would still show as is now.

Like if i were to choose “Appliance Bases” under the “Cabinet Categories” drop-down, all the options for “Description” and “Dimensions” would still show, but be grayed out and not available to click, instead of just disappearing when it is filtered.

Any help would be appreciated:)


Is this variation of set-cover NP-hard to approximate?

The classic set-cover problem is described as follows:

Let $ S = \{s_1, …, s_n\}$ be a target set, and let $ \Lambda = \{A_1, > …, A_m: A_i \subset S\}$ be a collection of subsets of $ S$ . The objective is to find some cover $ C \subset \Lambda $ such that $ \cup_{A\in C}A = S$ and $ |C|$ is minimized. That is, find the minimum number of $ A$ ‘s needed to cover every element of $ S$ .

The variation we will consider has two key alterations:

  1. Rather than finding some cover $ C$ such that $ |C|$ is minimized, we want to cover as much of $ S$ as possible, given some budget $ k$ . That is, let $ F\subset S$ be the elements that are covered by $ C$ , our objective is to maximize $ $ \big|F \cap S\big|$ $ such that $ |C| \leq k$ .

  2. Rather than considering an element $ s \in S$ covered when $ s$ appears in at least one $ A\in C$ , we require that $ s$ show up in 2 distinct $ A$ ‘s to be considered covered. (Any multiple is also interesting, even heterogeneous ones for each $ s\in S$ , but for now 2 is good enough).

So far I can show that it is an NP optimization (reduction from set-cover), and that a $ n-$ approximation exists by simply looking any element $ s$ that appears in some $ A_i$ and $ A_j$ and then selecting $ C = \{A_i, A_j\}$ , but this is a rather unsatisfying approximation.

Is this variation NP-hard to approximate to a constant factor?

Gas Station problem : Fixed path variation

Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path is fixed (ie) you have to go from C1 to Cn through C2, C3,.. and so on. The objective is to fill fuel in these cities in such a way the spendings on fuel is minimized. I thought about storing the minimum prices within a window whose requirements add up to K and then find the minimum cost required to traverse. I’m not sure how it holds up or is it even right in the first place. What if being greedy and filling up fuel to reach the city empty till you reach the closest city with cheaper fuel, not the optimal solution? How do i prove that it is?

Lookup columns referencing Source variation site Ids in sharepoint 2016

I am using Variations feature in Sharepoint 2016. I have a lookup column for a list in my Source variation site. Now I am popagating that list in my target variation site. The list is getting propagated but the problem I am facing is that the lookup items for that column in Target variation site are still referring to lookup list from source variation site.

Is this variation of the assignment problem NP-hard, and does it have a name?

I’m trying to solve a problem very similar to the assignment problem, with a few twists.

The problem has a certain amount of workers, and a certain amount of tasks – workers is always >= tasks. Each agent has a cost to perform each task. The goal is to assign workers to tasks such that the total cost is minimized. However, there are far more workers than tasks, and multiple workers can be assigned to a task. A task has a “capacity” of how many people can be working on it. Thus far, what I have described can still be considered the assignment problem and the constraint of multiple workers to a task can be solved with the Hungarian Algorithm by cloning tasks to the amount of workers that can perform them at once. However, there’s one last constraint that breaks pretty much everything: workers have a type and only workers of the same type can work on the same task. Tasks do not have types, but the workers who work on them must all have the same type. I suspect this problem is NP-hard and has to be solved with probabilistic optimization algorithms.