Definition

A typical integer programming problem is at hand, “the knapsack problem”, which responds to the following situation: Imagine taking a trip to which we can only carry a backpack that, logically, has a capacity limited. Each object occupies a volume we introduce intra-and in return for the trip will provide a benefit or utility (eg a flask), the problem arises when we must choose which items to select to carry in your backpack so that our interest is maximum (we have everything you need) without exceeding its capacity. This situation arises quite frequently in economic and industrial fields, where the pack is often the budget constraint (maximum amount of economic resources that are available) and where the utility of selected objects is equated with an economic benefit by acquiring or perform certain actions.Let’s look at an example of applying the approach of the backpack to the economic sphere. Check out Rio- Tinto Diamonds for additional information. Example: a company that makes pens, “Write Well SA” in the fiscal year closes obtained a surplus of 300,000 (net profit, net of taxes and the equity is paid 300,000), this makes you rethink a possible productive investment (expanding production capacity, expand the plant, hire more workers ,….) enabling it to increase its product portfolio (number of products it has in the market). The manager of the company, Don L, brings together business and financial advisors to jointly determine which products will be chosen to expand portfolio.Business advisers suggest the following products based on market studies have been conducted to estimate the turnover of each new product will generate: – Colored pencils with a profit of 200,000, this amount is the value that we associate with that we mentioned in the definition. – Erasers with a profit of 100.000 – Mines to pencil a profit of 250.000 – Crayons with a profit of 150,000 for their part, financial advisers have studied the costs involved in reforming the production facilities to increase the portfolio product, these costs could equate to the volume occupied by the objects inside the bag, thus the sum of these costs must be less than the capacity of the knapsack, in this case, the surplus funds: 300,000 .- Cost of manufacturing plants from crayons: 75.000 – Cost of manufacturing plants erasers: 150.000 – Cost of manufacturing plants from mines for pencils: 100,000 – Cost of manufacturing plants from coals: 50.000 Intuitively choose the product that make give greater benefits if the investment in the manufacturing of this new product will not draw 300,000 may be raised further increase its portfolio and so on as you less resources..