A semantic triple, or RDF triple or simply triple, is the atomic data entity in the Resource Description Framework (RDF) data model. As its name indicates, a triple is a sequence of three entities that codifies a statement about semantic data in the form of subject–predicate–object expressions (e.g., "Bob is 35", or "Bob knows John"). == Subject, predicate and object == This format enables knowledge to be represented in a machine-readable way. Particularly, every part of an RDF triple is individually addressable via unique URIs—for example, the statement "Bob knows John" might be represented in RDF as: http://example.name#BobSmith12 http://xmlns.com/foaf/spec/#term_knows http://example.name#JohnDoe34. Given this precise representation, semantic data can be unambiguously queried and reasoned about. The components of a triple, such as the statement "The sky has the color blue", consist of a subject ("the sky"), a predicate ("has the color"), and an object ("blue"). This is similar to the classical notation of an entity–attribute–value model within object-oriented design, where this example would be expressed as an entity (sky), an attribute (color) and a value (blue). From this basic structure, triples can be composed into more complex models, by using triples as objects or subjects of other triples—for example, Mike → said → (triples → can be → objects). Given their particular, consistent structure, a collection of triples is often stored in purpose-built databases called triplestores. == Difference from relational databases == A relational database is the classical form for information storage, working with different tables, which consist of rows. The query language SQL is able to retrieve information from such a database. In contrast, RDF triple storage works with logical predicates. No tables nor rows are needed, but the information is stored in a text file. An RDF-triple store can be converted into an SQL database and the other way around. If the knowledge is highly unstructured and dedicated tables aren't flexible enough, semantic triples are used over classic relational storage. In contrast to a traditional SQL database, an RDF triple store isn't created with a table editor. The preferred tool is a knowledge editor, for example Protégé. Protégé looks similar to an object-oriented modeling application used for software engineering, but it's focused on natural language information. The RDF triples are aggregated into a knowledge base, which allows external parsers to run requests. Possible applications include the creation of non-player characters within video games. == Limitations == One concern about triple storage is its lack of database scalability. This problem is especially pertinent if millions of triples are stored and retrieved in a database. The seek time is larger than for classical SQL-based databases. A more complex issue is a knowledge model's inability to predict future states. Even if all the domain knowledge is available as logical predicates, the model fails in answering what-if questions. For example, suppose in the RDF format a room with a robot and table is described. The robot knows what the location of the table is, is aware of the distance to the table and knows also that a table is a type of furniture. Before the robot can plan its next action, it needs temporal reasoning capabilities. Thus, the knowledge model should answer hypothetical questions in advance before an action is taken.
30 Boxes
30 Boxes is a minimalist calendaring IOS application created by 83 Degrees. Originating as a web application in March 2006, 30 Boxes was founded by Webshots cofounder Narendra Rocherolle. The website shut down some time in 2020, but relaunched for the IOS in February 2021. The original website was tailored towards "social media junkies". == Reception == Barry Collins of The Sunday Times appreciated the website's plain-language event adding feature, but did not appreciate that he was unable to see more than one month of events at a time. Collins was also unhappy that the website was not capable of warning him when he had two events scheduled at the same time. In a list of the best web-based calendar software for small businesses, Forbes ranked 30 Boxes second, after Google Calendar. They described 30 Boxes like “buying a new car with manual transmission and lots of extras—you don't just want to drive it, you want to fool around with it to see what it can do”.
ISO 15765-2
ISO 15765-2, or ISO-TP (Transport Layer), is an international standard for sending data packets over a CAN bus. The protocol allows for the transport of messages that exceed the eight byte maximum payload of CAN frames. ISO-TP segments longer messages into multiple frames, adding metadata (CAN-TP Header) that allows the interpretation of individual frames and reassembly into a complete message packet by the recipient. It can carry up to 232-1 (4294967295) bytes of payload per message packet starting from the 2016 version. Prior versions were limited to a maximum payload size of 4095 bytes. In the OSI model, ISO-TP covers the layer 3 (network layer) and 4 (transport layer). The most common application for ISO-TP is the transfer of diagnostic messages with OBD-II equipped vehicles using KWP2000 and UDS, but is used broadly in other application-specific CAN implementations where one might need to send messages longer than what the CAN protocol physical layer allows (eight bytes for CAN, 64 bytes for CAN FD, and 2048 bytes for CAN-XL). ISO-TP can be operated with its own addressing as so-called Extended Addressing or without address using only the CAN ID (so-called Normal Addressing). Extended addressing uses the first data byte of each frame as an additional element of the address, reducing the application payload by one byte. For clarity the protocol description below is based on Normal Addressing with eight byte CAN frames. In total, six types of addressing are allowed by the ISO 15765-2 Protocol. ISO-TP prepends one or more metadata bytes to the payload data in the eight byte CAN frame, reducing the payload to seven or fewer bytes per frame. The metadata is called the Protocol Control Information, or PCI. The PCI is one, two or three bytes. The initial field is four bits indicating the frame type, and implicitly describing the PCI length. ISO 15765-2 is a part of ISO 15765 (headlined Road vehicles — Diagnostic communication over Controller Area Network (DoCAN)), which has the following parts: ISO 15765-1 Part 1: General information and use case definition ISO 15765-2 Part 2: Transport protocol and network layer services ISO 15765-3 Part 3: Implementation of unified diagnostic services (UDS on CAN) – replaced by ISO 14229-3 Road vehicles — Unified diagnostic services ISO 15765-4 Part 4: Requirements for emissions-related systems == List of protocol control information (PCI) field types == The ISO-TP defines four frame types: A message of seven bytes or less is sent in a single frame, with the initial byte containing the type (0) and payload length (1-7 bytes). With the 0 in the type field, this can also pass as a simpler protocol with a length-data format and is often misinterpreted as such. A message longer than 7 bytes requires segmenting the message packet over multiple frames. A segmented transfer starts with a First Frame. The PCI is two bytes in this case, with the first 4 bit field the type (type 1) and the following 12 bits the message length (excluding the type and length bytes). The recipient confirms the transfer with a flow control frame. The flow control frame has three PCI bytes specifying the interval between subsequent frames and how many consecutive frames may be sent (Block Size). For CAN FD, the ISO 15765-2 protocol has been extended for Single and First frame, to allow larger size values, but still backwards compatible with traditional ISO 15765. See CAN FD. The initial byte contains the type (type = 3) in the first four bits, and a flag in the next four bits indicating if the transfer is allowed (0 = Continue To Send, 1 = Wait, 2 = Overflow/abort). The next byte is the block size, the count of frames that may be sent before waiting for the next flow control frame. A value of zero allows the remaining frames to be sent without flow control or delay. The third byte is the minimum Separation Time (STmin), the minimum delay time between frames. STmin values up to 127 (0x7F) specify the minimum number of milliseconds to delay between frames, while values in the range 241 (0xF1) to 249 (0xF9) specify delays increasing from 100 to 900 microseconds. Note that the Separation Time is defined as the minimum time between the end of one frame to the beginning of the next. Robust implementations should be prepared to accept frames from a sender that misinterprets this as the frame repetition rate i.e. from start-of-frame to start-of-frame. Even careful implementations may fail to account for the minor effect of bit-stuffing in the physical layer. The sender transmits the rest of the message using Consecutive Frames. Each Consecutive Frame has a one byte PCI, with a four bit type (type = 2) followed by a 4-bit sequence number. The sequence number starts at 1 and increments with each frame sent (1, 2,..., F, 0, 1,...), with which lost or discarded frames can be detected. Each consecutive frame starts at 0, initially for the first set of data in the first frame will be considered as 0th data. So the first set of CF(Consecutive frames) start from 0x1. There afterwards when it reaches 0x2F, will be started from 0x20 (e.g. 0x21, 0x22, 0x23...0x2F, 0x20, 0x21...). The 12-bit length field (as indicated in the First Frame) allows up to 4095 bytes of user data in a segmented message, but in practice the typical application-specific limit is considerably lower because of receive buffer or hardware limitations. == Timing parameters == Timing parameters, such as P1 and P2 timers, have to be mentioned. == Standards == ISO 15765-2:2016 Road vehicles -- Diagnostic communication over Controller Area Network (DoCAN) -- Part 2: Transport protocol and network layer services
Localhost
In computer networking, localhost is a hostname that refers to the current computer used to access it. The name localhost is reserved for loopback purposes. It is used to access the network services that are running on the host via the loopback network interface. Using the loopback interface bypasses any local network interface hardware. == Loopback == The local loopback mechanism may be used to run a network service on a host without requiring a physical network interface, or without making the service accessible from the networks the computer may be connected to. For example, a locally installed website may be accessed from a Web browser by the URL http://localhost to display its home page. IPv4 network standards reserve the entire address block 127.0.0.0/8 (more than 16 million addresses) for loopback purposes. That means any packet sent to any of those addresses is looped back. The address 127.0.0.1 is the standard address for IPv4 loopback traffic; the rest are not supported by all operating systems. However, they can be used to set up multiple server applications on the host, all listening on the same port number. In the IPv6 addressing architecture there is only a single address assigned for loopback: ::1. The standard precludes the assignment of that address to any physical interface, as well as its use as the source or destination address in any packet sent to remote hosts. == Name resolution == The name localhost normally resolves to the IPv4 loopback address 127.0.0.1, and to the IPv6 loopback address ::1. This resolution is normally configured by the following lines in the operating system's hosts file: 127.0.0.1 localhost ::1 localhost The name may also be resolved by Domain Name System (DNS) servers, but there are special considerations governing the use of this name: An IPv4 or IPv6 address query for the name localhost must always resolve to the respective loopback address. Applications may resolve the name to a loopback address themselves, or pass it to the local name resolver mechanisms. When a name resolver receives an address (A or AAAA) query for localhost, it should return the appropriate loopback addresses, and negative responses for any other requested record types. Queries for localhost should not be sent to caching name servers. To avoid burdening the Domain Name System root servers with traffic, caching name servers should never request name server records for localhost, or forward resolution to authoritative name servers. When authoritative name servers receive queries for 'localhost' in spite of the provisions mentioned above, they should resolve them appropriately. In addition to the mapping of localhost to the loopback addresses (127.0.0.1 and ::1), localhost may also be mapped to other IPv4 (loopback) addresses and it is also possible to assign other, or additional, names to any loopback address. The mapping of localhost to addresses other than the designated loopback address range in the hosts file or in DNS is not guaranteed to have the desired effect, as applications may map the name internally. In the Domain Name System, the name .localhost is reserved as a top-level domain name, originally set aside to avoid confusion with the hostname localhost. Domain name registrars are precluded from delegating domain names in the top-level .localhost domain. == Historical notes == In 1981, the block 127.0.0.0/8 got a 'reserved' status, as not to assign it as a general purpose class A IP network. This block was officially assigned for loopback purposes in 1986. Its purpose as a Special Use IPv4 Address block was confirmed in 1994,, 2002, 2010,, and last in 2013. From the outset, in 1995, the single IPv6 loopback address ::1 was defined. Its purpose and definition was unchanged in 1998,, 2003,, and up to the current definition, in 2006. == Packet processing == The processing of any packet sent to a loopback address, is implemented in the link layer of the TCP/IP stack. Such packets are never passed to any network interface controller (NIC) or hardware device driver and must not appear outside of a computing system, or be routed by any router. This permits software testing and local services, even in the absence of any hardware network interfaces. Looped-back packets are distinguished from any other packets traversing the TCP/IP stack only by the special IP address they were addressed to. Thus, the services that ultimately receive them respond according to the specified destination. For example, an HTTP service could route packets addressed to 127.0.0.99:80 and 127.0.0.100:80 to different Web servers, or to a single server that returns different web pages. To simplify such testing, the hosts file may be configured to provide appropriate names for each address. Packets received on a non-loopback interface with a loopback source or destination address must be dropped. Such packets are sometimes referred to as Martian packets. As with any other bogus packets, they may be malicious and any problems they might cause can be avoided by applying bogon filtering. == Special cases == The releases of the MySQL database differentiate between the use of the hostname localhost and the use of the addresses 127.0.0.1 and ::1. When using localhost as the destination in a client connector interface of an application, the MySQL application programming interface connects to the database using a Unix domain socket, while a TCP connection via the loopback interface requires the direct use of the explicit address. One notable exception to the use of the 127.0.0.0/8 addresses is their use in Multiprotocol Label Switching (MPLS) traceroute error detection, in which their property of not being routable provides a convenient means to avoid delivery of faulty packets to end users.
IBM remote batch terminals
The IBM 2780 and the IBM 3780 are devices developed by IBM for performing remote job entry (RJE) and other batch functions over telephone lines; they communicate with the mainframe via Binary Synchronous Communications (BSC or Bisync) and replaced older terminals using synchronous transmit-receive (STR). In addition, IBM has developed workstation programs for the 1130, 360/20, 2922, System/360 other than 360/20, System/370 and System/3. == 2780 Data Transmission Terminal == The 2780 Data Transmission Terminal first shipped in 1967. It consists of: A line printer similar to the IBM 1443 that can print up to 240 lines per minute (lpm), or 300 lpm using an extremely restricted character set. A card reader/punch unit, similar to an IBM 1442, that can read up to 400 cards per minute (cpm) and can punch up to 355 cpm. A line buffer that stores data received or to be transmitted over the communications line. A binary synchronous adapter which controls the flow of data over the communications line. The 2780 is capable of local (offline) card to print operation. It comes in four models: Model 1: Can read punched cards and transmit the data to a remote host computer, and can receive and print data sent by the host. Model 2: Same as Model 1 but adds the ability to punch card data received from the host. Model 3: Can only print data received from the host, but not send data to it. Model 4: Can read and punch card data, but has no printing capabilities. The 2780 uses a dedicated communication line at speeds of 1200, 2000, 2400 or 4800 bits per second. It is a half duplex device, although full duplex lines can be used with some increase in throughput. It can communicate in Transcode (a 6-bit code), 8-bit EBCDIC, or 7-bit ASCII. == 2770 Data Communication System == The 2770, announced in 1969, "was said to surpass all other IBM terminals in the variety of available input-output devices." The 2770 was developed by the IBM General Products Division (GPD) in Rochester, MN. It comes standard with a desktop terminal with keyboard. The printer and other devices (any two in any combination) can be attached to the 2772 Multi-Purpose Control unit. Possible devices include: 50 Magnetic Data Inscriber 545 Card Punch Model 3 (non-printing) or Model 4 (printing) 1017 Paper Tape Reader 1018 Paper Tape Punch 1053 Printer Model 1 1255 Magnetic Character Reader Models 1, 2 or 3 2203 Printer Model A1 or A2 2213 Printer Model 1 or 2 2265 Display Station Model 2 2502 Card Reader Model A1 or A2 5496 Data Recorder == 3780 Data Communications Terminal == In May 1972, IBM announced the IBM 3780, an enhanced version of the 2780. The 3780 was developed by IBM's Data Processing Division (DPD). There is one model, with an optional card punch. The 3780 drops Transcode support and incorporates several performance enhancements. It supports compression of blank fields in data using run-length encoding. It provides the ability to interleave data between devices, introduces double buffering, and adds support for the Wait-before-transmit ACKnowledgement (WACK) and Temporary Text Delay (TTD) Binary Synchronous control characters. The integrated punched card unit can read cards at 600 cards per minute. The integrated printer is rated at 300, 350 or 425 lines per minute based on characters set (63, 52 or 39 characters). The 3781 Card Punch is an optional feature. It punches 160 columns per second, or 91 cards per minute if all 80 columns are punched. The IBM 2780 and 3780 were later emulated on various types of equipment, including eventually the personal computer. A notable early emulation was the DN60, by Digital Equipment Corporation in the late 1970s. == 3770 Data Communications System == In 1974 IBM Data Processing Division (DPD) offered a successor to the 3780, called the 3770 Data Communications System, supporting SDLC, BSC, BSC Multi-leaving and SNA, depending on the configuration. The 3770 is a family of desk console style terminals that offers a variety of keyboard and printer combinations as well as I/O equipment attachment and communications features. The terminals come built into a desk and include the following models: 3771 Communication Terminal (optional card reader, optional card punch, wire matrix printer) Models 1 (40 cps printer), 2 (80 cps printer), and 3 (120 cps printer). 3773 Communication Terminal (diskette, wire matrix printer) Models 1 (40 cps printer), 2 (80 cps printer), and 3 (120 cps printer). Each model has a P version which adds some programming features. 3774 Communication Terminal (optional card reader, optional card punch, optional belt printer, wire matrix printer) Models 1 (80 cps printer), and 2 (120 cps printer). Each model has a P version which adds some programming features, a 480-character display and a non-removable diskette. 3775 Communication Terminal (optional card reader, optional card punch, optional diskette, belt printer) Model 1 (120 lpm printer). The model P1 adds some programming features, a 480-character display and a non-removable diskette. 3776 Communication Terminal (optional card reader, optional card punch, optional diskette, belt printer) Models 1 (300 lpm printer) and 2 (400 lpm printer). Models 3 and 4 are similar to models 1 and 2. 3777 Communication Terminal (optional card reader, optional diskette, train printer) Model 1 (up to 1000 lpm printer depending on character set). Model 2 adds an optional card punch, model 3 adds an optional magnetic tape drive and model 4 replaces the train printer with a slower model called the IBM 3262. The model 4 also allows a second, optional, 3262. The following I/O devices can be attached to a 3770 terminal: IBM 2502 Card Reader: Models A1 (up to 150 card per minute), A2 (up to 300 cards per minute) or A3 (up to 400 cards per minute) IBM 3203 Printer Model 3: 1000 LPM using 48 character set IBM 3501 Card Reader: Up to 50 cards per minute desktop unit IBM 3521 Card Punch: Up to 50 cards per minute IBM 3782 Card Attachment unit, which allows the 2502 or 3521 to be attached to any terminal except the 3777 IBM 3784 Line Printer, can be attached to a 3774 as a second printer. Up to 155 LPM with 48 characters set print belt. == Workstation programs == IBM distributes workstation programs with systems software including OS/360 Attached Support Processor (ASP) Houston Automatic Spooling Priority (HASP and HASP II) Operating System/Virtual Storage 1 (OS/VS1) Operating System/Virtual Storage 2 (OS/VS2 MVS) Release 2 through 3.8 MVS versions from MVS/SP Version 1 through z/OS Priority Output Writers, Execution processors and input Readers (POWER) Remote Spooling Communications Subsystem (RSCS) Except for the RJE workstation programs in OS/360, these programs use a variation of BSC known as Multi-leaving. In addition, IBM provides separately ordered workstation programs using BSC. Systems Network Architecture (SNA) and TCP/IP. Workstation programs are available from IBM and third-party vendors to support all of these protocols: 2770/3770 2780/3780 Multileaving Network Job Entry (NJE) OS/360 RJE SNA TCP/IP
Hit-testing
In computer graphics programming, hit-testing (hit detection, picking, or pick correlation) is the process of determining whether a user-controlled cursor (such as a mouse cursor or touch-point on a touch-screen interface) intersects a given graphical object (such as a shape, line, or curve) drawn on the screen. Hit-testing may be performed on the movement or activation of a mouse or other pointing device. Hit-testing is used by GUI environments to respond to user actions, such as selecting a menu item or a target in a game based on its visual location. In web programming languages such as HTML, SVG, and CSS, this is associated with the concept of pointer-events (e.g. user-initiated cursor movement or object selection). Collision detection is a related concept for detecting intersections of two or more different graphical objects, rather than intersection of a cursor with one or more graphical objects. == Algorithm == There are many different algorithms that may be used to perform hit-testing, with different performance or accuracy outcomes. One common hit-test algorithm for axis aligned bounding boxes. A key idea is that the box being tested must be either entirely above, entirely below, entirely to the right or left of the current box. If this is not possible, they are colliding. Example logic is presented in the pseudo-code below: In Python:
Knapsack problem
The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items to include in the 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 knapsack problem has been studied for more than a century, with early works dating back to 1897. The subset sum problem is a special case of the decision and 0-1 problems where for each kind of item, the weight equals the value: w i = v i {\displaystyle w_{i}=v_{i}} . In the field of cryptography, the term knapsack problem is often used to refer specifically to the subset sum problem. The subset sum problem is one of Karp's 21 NP-complete problems. == Applications == Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman and other knapsack cryptosystems. One early application of knapsack algorithms was in the construction and scoring of tests in which the test-takers have a choice as to which questions they answer. For small examples, it is a fairly simple process to provide the test-takers with such a choice. For example, if an exam contains 12 questions each worth 10 points, the test-taker need only answer 10 questions to achieve a maximum possible score of 100 points. However, on tests with a heterogeneous distribution of point values, it is more difficult to provide choices. Feuerman and Weiss proposed a system in which students are given a heterogeneous test with a total of 125 possible points. The students are asked to answer all of the questions to the best of their abilities. Of the possible subsets of problems whose total point values add up to 100, a knapsack algorithm would determine which subset gives each student the highest possible score. A 1999 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems related to the field of combinatorial algorithms and algorithm engineering, the knapsack problem was the 19th most popular and the third most needed after suffix trees and the bin packing problem. == Definition == The most common problem being solved is the 0-1 knapsack problem, which restricts the number x i {\displaystyle x_{i}} of copies of each kind of item to zero or one. Given a set of n {\displaystyle n} items numbered from 1 up to n {\displaystyle n} , each with a weight w i {\displaystyle w_{i}} and a value v i {\displaystyle v_{i}} , along with a maximum weight capacity W {\displaystyle W} , maximize ∑ i = 1 n v i x i {\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} subject to ∑ i = 1 n w i x i ≤ W {\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} and x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} . Here x i {\displaystyle x_{i}} represents the number of instances of item i {\displaystyle i} to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity. The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number x i {\displaystyle x_{i}} of copies of each kind of item to a maximum non-negative integer value c {\displaystyle c} : maximize ∑ i = 1 n v i x i {\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} subject to ∑ i = 1 n w i x i ≤ W {\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} and x i ∈ { 0 , 1 , 2 , … , c } . {\displaystyle x_{i}\in \{0,1,2,\dots ,c\}.} The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except that the only restriction on x i {\displaystyle x_{i}} is that it is a non-negative integer. maximize ∑ i = 1 n v i x i {\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} subject to ∑ i = 1 n w i x i ≤ W {\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} and x i ∈ N . {\displaystyle x_{i}\in \mathbb {N} .} One example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each book is available" in the caption of that figure. == Computational complexity == The knapsack problem is interesting from the perspective of computer science for many reasons: 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 that is both correct and fast (polynomial-time) in all cases. 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). This problem is co-NP-complete. There is a pseudo-polynomial time algorithm using dynamic programming. There is a fully polynomial-time approximation scheme, which uses the pseudo-polynomial time algorithm as a subroutine, described below. Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly. 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. One theme in research literature is to identify what the "hard" instances of the knapsack problem look like, or viewed another way, to identify what properties of instances in practice might make them more amenable than their worst-case NP-complete behaviour suggests. The goal in finding these "hard" instances is for their use in public-key cryptography systems, such as the Merkle–Hellman knapsack cryptosystem. More generally, better understanding of the structure of the space of instances of an optimization problem helps to advance the study of the particular problem and can improve algorithm selection. Furthermore, notable is the fact that the hardness of the knapsack problem depends on the form of the input. If the weights and profits are given as integers, it is weakly NP-complete, while it is strongly NP-complete if the weights and profits are given as rational numbers. However, in the case of rational weights and profits it still admits a fully polynomial-time approximation scheme. === Unit-cost models === The NP-hardness of the Knapsack problem relates to computational models in which the size of integers matters (such as the Turing machine). In contrast, decision trees count each decision as a single step. Dobkin and Lipton show an 1 2 n 2 {\displaystyle {1 \over 2}n^{2}} lower bound on linear decision trees for the knapsack problem, that is, trees where decision nodes test the sign of affine functions. This was generalized to algebraic decision trees by Steele and Yao. If the elements in the problem are real numbers or rationals, the decision-tree lower bound extends to the real random-access machine model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor"). This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions. An upper bound for a decision-tree model was given by Meyer auf der Heide who showed that for every n there exists an O(n4)-deep linear decision tree that solves the subset-sum problem with n items. Note that this does not imply any upper bound for an algorithm that should solve the problem for any given n. == Solving == Several algorithms are available to solve knapsack problems, based on the dynamic programming approach, the branch and bound approach or hybridizations of both approaches. === Dynamic programming in-advance algorithm === The unbounded knapsack problem (UKP) places no restriction on the number of copies of each kind of item. Besides, here we assume that x i > 0 {\displaystyle x_{i}>0} m [ w ′ ] = max ( ∑ i = 1 n v i x i ) {\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)} subject to ∑