0-1 backpack problem

1 a greedy

Assuming that a backpack can carry 100 kg items, we have the following 5 kinds of beans, and the total amount and total value of each bean are different. In order to maximize the total value of the items in the backpack, how can we choose which beans to carry in the backpack and how many of each bean to carry?

items Total quantity (kg) Total Value (YUAN)
soybean 100 100
Mung bean 30 90
Red bean 60 120
Black beans 20 80
Green beans 50 75

First sort the data, first install the high unit price, install until can’t install.

bag01_1.js

function bag01_1(max, beans) {
  const value = [];
  let rest = max;
  const res = [];
  for (let i = 0; i < beans.length; i++) {
    value.push([i, beans[i][2] / beans[i][1]]);
  }
  value.sort((a, b) = > b[1] - a[1]);

  for (let i = 0; i < value.length; i++) {
    const weight = beans[value[i][0]] [1];
    const type = beans[value[i][0]] [0];
    const val = value[i][1];
    if (weight < rest) {
      rest = rest - weight;
      res.push([type, weight, val]);
    } else {
      res.push([type, rest, val]);
      break; }}return res;
}

module.exports = bag01_1;
Copy the code

bag01_1.test.js

const bag01_1 = require('.. /src/bag01_1');

test('leetcode1'.() = > {
  expect(bag01_1(100The [['beans'.100.100], ['green beans'.30.90], ['red bean'.60.120], ['black'.20.80], ['green beans'.50.75]]))
  .toStrictEqual([['black'.20.4], ['green beans'.30.3], ['red bean'.50.2]]);
});
Copy the code

2 back

We have a backpack, the total carrying weight of the backpack is W kg. Now we have n items, each of which is of varying weight and indivisible. We now expect to select a few items and load them into the backpack. How to maximize the total weight of items in a backpack without exceeding the weight it can carry?

Note: indivisibility here means that we cannot calculate unit price as in the previous question.

Obviously, this problem can no longer be solved by greedy algorithms (because taking the highest value every time doesn’t guarantee the highest total value). But it can be solved by backtracking.

For every item, there are two choices: to put it in a backpack or not to put it in a backpack. For n items, there are 2^n total configurations, remove the ones with a total weight of more than W kg, and select the ones with a total weight closest to W kg from the remaining configurations. The 2^n configurations are not enumerated repeatedly, and backtracking can be used.

We can put the items in order, and the whole problem breaks down into n stages, each of which corresponds to the selection of items. The first item is processed, either loaded or not loaded, and then the remaining items are processed recursively.

Using a bit of the search pruning technique, we stop exploring the remaining items when we find that the selected item weighs more than W kg, which gives us some speed up.

bag01_2.js

function bag01_2(max, n, items) {
  // Stores the maximum total weight of items in the backpack
  let maxW = 0;
  f(0.0, items, n, max);
  return maxW;
  // CW represents the weight and weight of the currently loaded item
  // I indicates which item is examined
  // w backpack weight
  // items indicates the weight of each item
  // n indicates the number of items
  // If the backpack can hold 100 items, the number of items is 10, and the item weight is stored in array A, then we can call this function:
  // f(0, 0, a, 10, 100)
  function f(i, cw, items, n, w) {
    if (cw === w || i === n) { // cw === w indicates full; I === n indicates that all items have been examined
      if (cw > maxW) maxW = cw;
      return;
    }
    f(i + 1, cw, items, n, w); // I + 1 item is not loaded
    if (cw + items[i] <= w) {// When the weight has exceeded the backpack, do not carry any more
      f(i + 1, cw + items[i], items, n, w); // I + 1}}}module.exports = bag01_2;
Copy the code

bag01_2.test.js

const bag01_2 = require('.. /src/bag01_2');

test('bag01_2'.() = > {
  expect(bag01_2(100.10[10.10.10.10.10.10.10.10.10.10])).toBe(100);
  expect(bag01_2(100.10[110.200.10.80.10.10.10.50.20.30])).toBe(100);
  expect(bag01_2(100.10[110.200.101.80.95.120.130.150.220.130])).toBe(95);
  expect(bag01_2(100.10[110.200.101.20.15.120.37.50.220.130])).toBe(87);
  expect(bag01_2(9.5[2.2.4.6.3])).toBe(9);
});
Copy the code
Topic Difficulty escalation

The above backpack problem only involves the weight of the backpack and the weight of items. Now we need to introduce the value of items. For a group of items with different weight, different value and indivisibility, we choose to put some items into the backpack. Under the premise of meeting the maximum weight limit of the backpack, what is the maximum total value of items that can be loaded in the backpack?

bag01_5.js

function bag01_5(w, n, items, values) {
  // Store the maximum value of items in the backpack
  let maxV = 0;
  f(0.0.0);
  return maxV;
  // CW represents the weight and weight of the currently loaded item
  // CV represents the value and value of the items currently loaded
  // I indicates which item is examined
  function f(i, cw, cv) {
    if (cw === w || i === n) { // cw === w indicates full; I === n indicates that all items have been examined
      if (cv > maxV) maxV = cv;
      return;
    }
    f(i + 1, cw, cv); // I + 1 item is not loaded
    if (cw + items[i] <= w) {// When the weight has exceeded the backpack, do not carry any more
      f(i + 1, cw + items[i], cv + values[i]); // I + 1}}}module.exports = bag01_5;
Copy the code

bag01_5.test.js

const bag01_5 = require('.. /src/bag01_5');

test('bag01_5'.() = > {
  expect(bag01_5(9.5[2.2.4.6.3], [3.4.8.9.6])).toBe(18);
});
Copy the code

3 Dynamic Planning

As in problem 2, the time complexity of the backtracking algorithm is O(2^n) at the exponential level. To reduce the time complexity, dynamic programming can be used to solve this problem.

We divide the whole process into n stages, and each stage decides whether or not to put an item in the backpack. After each item decision (to put or not to put in the backpack) is made, the weight of the items in the backpack can be in many different ways, that is, it can reach many different states, corresponding to the recursion tree, that is, there are many different nodes.

We combine the repeated states (nodes) of each layer, record only the different states, and then deduce the state set of the next layer based on the state set of the previous layer. By combining the repeated states in each layer, we can ensure that the number of different states in each layer does not exceed W (w is the weight of the backpack), which is 9 in our example. Thus, we have successfully avoided an exponential increase in the number of states per layer.

We use a two-dimensional array states[n][W +1] to record the different states that each layer can achieve.

The weight of the 0 item (subscript numbered from 0) is 2. Either the item will be loaded into the backpack or not. After the decision is made, the two states of the backpack will correspond to the total weight of the items in the backpack is 0 or 2. We use states[0][0]=true and states[0][2]=true.

The weight of the first item is also 2, based on the previous state of the backpack, after the decision of this item, there are 3 different states, the total weight of the items in the backpack is 0(0+0), 2(0+2 or 2+0), 4(2+2). States [1][0]=true, States [1][2]=true, and States [1][4]=true.

All we need to do is look at the last layer and find a value true that is closest to w (9 in this case), which is the maximum total weight of the items in the backpack.

bag01_3.js

function bag01_3(max, n, items) {
  // Initialize a two-dimensional array to record the state of each phase
  const states = [];
  for (let i = 0; i < n; i++) {
    states.push([]);
    for (let j = 0; j < max + 1; j++) {
      states[i].push(false); }}// The first line of data is processed specially
  states[0] [0] = true;
  if (items[0] < max) {
    states[0][items[0]] = true;
  }
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < max + 1; j++) {
      if (states[i - 1][j] === true) { // Don't put the ith item in the backpack
        states[i][j] = states[i - 1][j];
      }
      if (states[i - 1][j] && j + items[i] <= max) { // Put the ith item into the backpack
        states[i][j + items[i]] = true; }}}for (let i = max; i >= 0; i--) {
    if (states[n - 1][i]) {
      returni; }}}module.exports = bag01_3;
Copy the code

bag01_3.test.js

const bag01_3 = require('.. /src/bag01_3');

test('bag01_3'.() = > {
  expect(bag01_3(100.10[10.10.10.10.10.10.10.10.10.10])).toBe(100);
  expect(bag01_3(100.10[110.200.10.80.10.10.10.50.20.30])).toBe(100);
  expect(bag01_3(100.10[110.200.101.80.95.120.130.150.220.130])).toBe(95);
  expect(bag01_3(100.10[110.200.101.20.15.120.37.50.220.130])).toBe(87);
  expect(bag01_3(9.5[2.2.4.6.3])).toBe(9);
});
Copy the code

The time complexity of this method is O(n*w), where n is the number of items and W is the total weight the backpack can carry.

Spatial complexity optimization

In terms of space complexity, it is necessary to apply for an additional TWO-DIMENSIONAL array of N times W +1, which consumes a lot of space. In fact, all we need is a one-dimensional array of size W +1 to solve this problem. Dynamically programming state transitions can be done based on this one-dimensional array.

bag01_4.js

function bag01_4(max, n, items) {
  // Initialize an array to record the status. Each phase uses one array
  const states = [];
  for (let j = 0; j < max + 1; j++) {
    states.push(false);
  }
  // Layer 1 data special processing
  states[0] = true;
  if (items[0] < max) {
    states[items[0]] = true;
  }
  for (let i = 1; i < n; i++) {
    for (let j = max; j >= 0; j--) { // j needs to be processed from large to small. If we process j from small to large, we will have the problem of double-counting for loop
      if (states[j] && j + items[i] <= max) { // Put the ith item into the backpack
        states[j + items[i]] = true; }}}for (let i = max; i >= 0; i--) {
    if (states[i]) {
      returni; }}}module.exports = bag01_4;
Copy the code

bag01_4.test.js

const bag01_4 = require('.. /src/bag01_4');

test('bag01_4'.() = > {
  expect(bag01_4(100.10[10.10.10.10.10.10.10.10.10.10])).toBe(100);
  expect(bag01_4(100.10[110.200.10.80.10.10.10.50.20.30])).toBe(100);
  expect(bag01_4(100.10[110.200.101.80.95.120.130.150.220.130])).toBe(95);
  expect(bag01_4(100.10[110.200.101.20.15.120.37.50.220.130])).toBe(87);
  expect(bag01_4(9.5[2.2.4.6.3])).toBe(9);
});
Copy the code
Topic Difficulty escalation

The above backpack problem only involves the weight of the backpack and the weight of items. Now we need to introduce the value of items. For a group of items with different weight, different value and indivisibility, we choose to put some items into the backpack. Under the premise of meeting the maximum weight limit of the backpack, what is the maximum total value of items that can be loaded in the backpack?

bag01_6.js

function bag01_6(max, n, items, values) {
  // Initialize an array to record the status. Each phase uses one array
  const states = [];
  for (let j = 0; j < max + 1; j++) {
    states.push(-1);
  }
  // Layer 1 data special processing
  states[0] = 0;
  if (items[0] < max) {
    states[items[0]] = values[0];
  }
  for (let i = 1; i < n; i++) {
    for (let j = max; j >= 0; j--) { // j needs to be processed from large to small. If we process j from small to large, we will have the problem of double-counting for loop
      if (states[j] >= 0 && j + items[i] <= max) { // Put the ith item into the backpack
        v = states[j] + values[i];
        if(v > states[j + items[i]]) { states[j + items[i]] = v; }}}}return Math.max(... states); }module.exports = bag01_6;
Copy the code

bag01_6.test.js

const bag01_6 = require('.. /src/bag01_6');

test('bag01_6'.() = > {
  expect(bag01_6(9.5[2.2.4.6.3], [3.4.8.9.6])).toBe(18);
});
Copy the code