{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cbr\u003e \n\u003cp\u003e You have N items that you want to put them into a knapsack. Item i has value v\u003csub\u003ei\u003c/sub\u003e and weight \u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003e You want to find a subset of items to put such that:\u003c/p\u003e \n\u003cul\u003e \n \u003cli\u003e The total value of the items is as large as possible.\u003c/li\u003e \n \u003cli\u003e The items have combined weight at most W, that is capacity of the knapsack.\u003c/li\u003e \n\u003c/ul\u003e \n\u003cp\u003e Find the maximum total value of items in the knapsack.\u003c/p\u003e \n\u003ch2\u003e Input\u003c/h2\u003e \n\u003cpre\u003e\r\nN W\r\nv\u003csub\u003e1 \u003c/sub\u003ew\u003csub\u003e1\r\n\u003c/sub\u003ev\u003csub\u003e2 \u003c/sub\u003ew\u003csub\u003e2\u003c/sub\u003e\r\n:\r\nv\u003csub\u003eN \u003c/sub\u003ew\u003csub\u003eN\u003c/sub\u003e\u003c/pre\u003e \n\u003cp\u003e The first line consists of the integers N and W. In the following lines, the value and weight of the \u003cspan\u003ei-th\u003c/span\u003e item are given.\u003c/p\u003e \n\u003ch2\u003e Output\u003c/h2\u003e \n\u003cp\u003e Print the maximum total values of the items in a line.\u003c/p\u003e \n\u003ch2\u003e Constraints\u003c/h2\u003e \n\u003cul\u003e \n \u003cli\u003e 1 ≤ N ≤ 100\u003c/li\u003e \n \u003cli\u003e 1 ≤ v\u003csub\u003ei\u003c/sub\u003e ≤ 1000\u003c/li\u003e \n \u003cli\u003e 1 ≤ \u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e ≤ 1000\u003c/li\u003e \n \u003cli\u003e 1 ≤ W ≤ 10000\u003c/li\u003e \n\u003c/ul\u003e \n\u003ch2\u003e Sample Input 1\u003c/h2\u003e \n\u003cpre\u003e\r\n4 5\r\n4 2\r\n5 2\r\n2 1\r\n8 3\r\n\u003c/pre\u003e \n\u003ch2\u003e Sample Output 1\u003c/h2\u003e \n\u003cpre\u003e\r\n13\r\n\u003c/pre\u003e \n\u003cbr\u003e \n\u003ch2\u003e Sample Input 2\u003c/h2\u003e \n\u003cpre\u003e\r\n2 20\r\n5 9\r\n4 10\r\n\u003c/pre\u003e \n\u003ch2\u003e Sample Output 2\u003c/h2\u003e \n\u003cpre\u003e\r\n9\r\n\u003c/pre\u003e"}}]}