NP-Completeness of Carry-Weight/Encumberence Mechanics

RPGs both tabletop and computer based have been known to have a game mechanic known as "Carry-Weight" or "Encumberence" as part of the gameplay. This is to impose constraints on how much a character can carry around and is used to prevent gamebreaking situations in which one can become extremely rich quickly or OP using loot.

It works by giving each item a numeric weight. This is compared to a number assigned to the character that determines the maximum amount of weight that can be carried at any given time without having adverse conditions affect the character due to being overencumbered. This carry-weight can often be increased by leveling up or using specific buffs. It can also be decreased by specific debuffs.

This forces the player to make decisions about how much gear to carry with on an adventure along with potential loot. As well as figure out how to load out the character so that the best situation for any particular scenario is reached. This problem turns out to be NP-Complete since it is basically the Knapsack Problem.

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large
as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible
projects or tasks under a fixed budget or time constraint, respectively.

The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no known algorithm both correct and fast (polynomial-time) in all cases.

While the decision problem is NP-complete, the optimization problem is not, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger V, thus solving the NP-complete decision problem).

There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k . On the other hand, if an algorithm finds the optimal value of the optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k . Thus, both versions of the problem are of similar difficulty.

In the case of RPGs however, this problem might be more complex due to the following things that a player must consider besides the value of the item. This can include the buffs or debuffs in stats, the decision of which pieces of loot to sell and which ones to keep, etc. This might possibly increase the NP-Completeness of the problem.

So what does this information mean for a GM?

It depends. Depending on your players experience with working on combinatorial optimization problems, having encumberence mechanics in your game can either make it more interesting or extremely boring. Also since this is a problem that requires a significent amount of thinking some players might take longer then others at coming up with their optimum load out. This can slow down gameplay significantly. So you must be careful when implementing them into your game if you want a constant pace.

For example: The party is about to embark on another adventure and so they all prepare their characters by selecting their equipment from their loot storage vault. (My personal suggestion is to give your adventuring party a base of operations to prepare for adventures, store loot, hang out, train skills etc. Like in the Elder Scrolls games.) Some players are going to take longer then others to decide on their load out. If you don't want that to slow down the game, it is best to use a different inventory system that doesn't have a encumbrence system.