Dynamic Programming: The Knapsack Problem - 2. The Complete Knapsack Model

maximum value minimum value

complete knapsack problem

analyze

state representation

  • v ( i ) v(i) v(i): the first i i i object volumes
  • w ( i ) w(i) w(i): the first i i i object values
  • f ( i , j ) f(i,j) f(i,j): before i i i items are selected, the volume does not exceed j j maximum value of j

State transfer: as long as the backpack can fit, you can choose k k k th i i i items. both satisfied j ≥ k v ( i ) j \ge k v(i) j≥kv(i), which can be obtained from f ( i − 1 , j − k v ( i ) ) f(i - 1, j - kv(i)) f(i−1,j−kv(i)) shift. k ≥ 0 k \ge 0 k≥0

code

import java.util.*;

public class Main {
  public static int dp(int[] v, int[] w, int n, int m) {
    int[][] f = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        for (int k = 0; j >= k * v[i]; k++) {
          f[i][j] = Math.max(f[i - 1][j - k * v[i]] + k * w[i], f[i][j]);
        }
      }
    }
    return f[n][m];
  }
  
  // for IO
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int[] v = new int[n + 1];
    int[] w = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      v[i] = scanner.nextInt();
      w[i] = scanner.nextInt();
    }
    System.out.println(dp(v, w, n, m));
  }
}

optimization

formula equivalent deformation

  1. f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − v ( i ) ) + w ( i ) , . . . , f ( i − 1 , j − k v ( i ) ) + k w ( i ) , . . . ) f(i,j)=max(f(i-1,j),f(i-1,j-v(i))+w(i),...,f(i-1,j-kv(i))+kw(i),...) f(i,j)=max(f(i−1,j),f(i−1,j−v(i))+w(i),...,f(i−1,j−kv(i))+kw(i),...)

  2. f ( i , j − v ( i ) ) + w ( i ) = m a x ( f ( i − 1 , j − v ( i ) ) + w ( i ) , f ( i − 1 , j − 2 v ( i ) ) + 2 w ( i ) , . . . , f ( i − 1 , j − ( k + 1 ) v ( i ) ) + ( k + 1 ) w ( i ) , . . . ) f(i,j-v(i)) + w(i)=max(f(i-1,j-v(i)) + w(i),f(i-1,j-2v(i))+2w(i),...,f(i-1,j-(k+1)v(i))+(k+1)w(i),...) f(i,j−v(i))+w(i)=max(f(i−1,j−v(i))+w(i),f(i−1,j−2v(i))+2w(i),...,f(i−1,j−(k+1)v(i))+(k+1)w(i),...)

Comparing 1 and 2, it is found that the max in 1 is the same as 2 from the second item, so there is f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i , j − v ( i ) ) + w ( i ) ) f(i,j)=max(f(i-1,j),f(i,j-v(i))+w(i)) f(i,j)=max(f(i−1,j),f(i,j−v(i))+w(i))

public static int dp(int[] v, int[] w, int n, int m) {
  int[][] f = new int[n + 1][m + 1];
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
       f[i][j] = f[i - 1][j];
       if (j >= v[i]) f[i][j] = Math.max(f[i - 1][j], f[i][j - v[i]] + w[i]);
    }
  }
  return f[n][m];
}

Optimization space

public static int dp(int[] v, int[] w, int n, int m) {
  int[] f = new int[m + 1];
  for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {
      f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
  }
  return f[m];
}

change

analyze

state representation

  • q ( i ) q(i) q(i): the first i i i coin denominations ( i i i from 0 0 0 starts)
  • f ( i , j ) f(i,j) f(i,j): before i i i coins are chosen, and the amount is exactly j j Minimum number of coins for j

State transition: As long as the total value of the selected coins does not exceed the target value, you can select k k k th i i i items. both satisfied j ≥ k q ( i − 1 ) j \ge k q(i-1) j≥kq(i−1), can be obtained from f ( i − 1 , j − k q ( i − 1 ) ) f(i - 1, j - kq(i-1)) f(i−1,j−kq(i−1)) shift. k ≥ 0 k \ge 0 k≥0

code

class Solution {
    public int coinChange(int[] q, int x) {
        if (x == 0) return 0;
        int n = q.length;
       
        int[][] f = new int[n + 1][x + 1];
				
        // Find the minimum value, so initialize to positive infinity
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= x; j++) f[i][j] = 0x3f3f3f;
        }
				
      	// When the first coin is selected, the number of coins that can be collected for x
        for (int j = 0; j <= x; j++) {
            if (j % q[0] == 0) f[1][j] = j / q[0];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                for (int k = 0; j >= k * q[i - 1]; k++) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - k * q[i - 1]] + k);
                }
            }
        }

        return f[n][x] == 0x3f3f3f ? -1 : f[n][x];
    }
}

optimization

formula equivalent deformation

  1. f ( i , j ) = m i n ( f ( i − 1 , j ) , f ( i − 1 , j − q ( i − 1 ) ) + 1 , f ( i − 1 , j − 2 q ( i − 1 ) ) + 2 , . . . ) f(i,j) = min(f(i-1,j), f(i - 1,j - q(i - 1)) + 1,f(i-1,j-2q(i-1))+2,...) f(i,j)=min(f(i−1,j),f(i−1,j−q(i−1))+1,f(i−1,j−2q(i−1))+2,...)
  2. f ( i , j − q ( i − 1 ) ) + 1 = m i n ( f ( i − 1 , j − q ( i − 1 ) ) + 1 , f ( i − 1 , j − 2 q ( i − 1 ) ) + 2 , . . . ) f(i,j - q(i - 1)) + 1 = min(f(i - 1,j - q(i - 1)) + 1, f(i - 1,j - 2q(i - 1)) + 2, ...) f(i,j−q(i−1))+1=min(f(i−1,j−q(i−1))+1,f(i−1,j−2q(i−1))+2,...)

Comparing 1 and 2, it is found that the min of 1 is the same as 2 from the second item, so there is f ( i , j ) = m i n ( f ( i − 1 , j ) , f ( i , j − q ( i − 1 ) ) + 1 ) f(i,j) = min(f(i-1,j) , f(i,j-q(i-1)) + 1) f(i,j)=min(f(i−1,j),f(i,j−q(i−1))+1)

class Solution {
    public int coinChange(int[] q, int x) {
        if (x == 0) return 0;
        int n = q.length;
      
        int[][] f = new int[n + 1][x + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= x; j++) f[i][j] = 0x3f3f3f;
        }

        for (int j = 0; j <= x; j++) {
            if (j % q[0] == 0) f[1][j] = j / q[0];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= q[i - 1]) f[i][j] = Math.min(f[i - 1][j], f[i][j - q[i - 1]] + 1);      
            }
        }

        return f[n][x] == 0x3f3f3f ? -1 : f[n][x];
    }
}

Optimization space

class Solution {
    public int coinChange(int[] q, int x) {
        if (x == 0) return 0;
        int n = q.length;

        int[] f = new int[x + 1];

        for (int j = 0; j <= x; j++) {
            f[j] = j % q[0] == 0 ? j / q[0] : 0x3f3f3f;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = q[i - 1]; j <= x; j++) {
                f[j] = Math.min(f[j], f[j - q[i - 1]] + 1);
            }
        }

        return f[x] == 0x3f3f3f ? -1 : f[x];
    }
}

number of plans

monetary system

analyze

state representation

  • v ( i ) v(i) v(i): the first i i i currency denominations
  • f ( i , j ) f(i,j) f(i,j): before i i i currencies are chosen with a face value of exactly j j number of options for j

State transfer: as long as the backpack can fit, you can choose k k k th i i i currencies. both satisfied j ≥ k v ( i ) j \ge k v(i) j≥kv(i), which can be obtained from f ( i − 1 , j − k v ( i ) ) f(i - 1, j - kv(i)) f(i−1,j−kv(i)) shift. k ≥ 0 k \ge 0 k≥0

code

import java.util.*;

public class Main {
  public static long dp(int[] v, int n, int m) {
    long[][] f = new long[n + 1][m + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        for (int k = 0; j >= k * v[i]; k++) {
          f[i][j] += f[i - 1][j - k * v[i]];
        }
      }
    }
    return f[n][m];
  }
  
  // for IO
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int[] v = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      v[i] = scanner.nextInt();
    }
    System.out.println(dp(v, n, m));
  }
}

optimization

formula equivalent deformation

  1. f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − v ( i ) ) + . . . + f ( i − 1 , j − k v ( i ) ) + . . . f(i,j)=f(i-1,j) + f(i-1,j-v(i)) + ... + f(i-1,j-kv(i)) + ... f(i,j)=f(i−1,j)+f(i−1,j−v(i))+...+f(i−1,j−kv(i))+...

  2. f ( i , j − v ( i ) ) = f ( i − 1 , j − v ( i ) ) + f ( i − 1 , j − 2 v ( i ) ) + . . . + f ( i − 1 , j − ( k + 1 ) v ( i ) ) + . . . f(i,j-v(i)) = f(i-1,j-v(i)) + f(i-1,j-2v(i)) + ... + f(i-1,j-(k+1)v(i)) + ... f(i,j−v(i))=f(i−1,j−v(i))+f(i−1,j−2v(i))+...+f(i−1,j−(k+1)v(i))+...

Comparing 1 and 2, it is found that 1 is the same as 2 from the second term, so there is f ( i , j ) = f ( i − 1 , j ) + f ( i , j − v ( i ) ) f(i,j) = f(i-1,j) + f(i,j-v(i)) f(i,j)=f(i−1,j)+f(i,j−v(i))

public static long dp(int[] v, int n, int m) {
  long[][] f = new long[n + 1][m + 1];
  f[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= v[i]) f[i][j] += f[i][j - v[i]];
    }
  }
  return f[n][m];
}

Optimization space

public static long dp(int[] v, int n, int m) {
  long[] f = new long[m + 1];
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {
      f[j] += f[j - v[i]];
    }
  }
  return f[m];
}

Change Exchange II

analyze

state representation

  • q ( i ) q(i) q(i): the first i i i coin denominations ( i i i from 0 0 0 starts)
  • f ( i , j ) f(i,j) f(i,j): before i i i coins are chosen, and the amount is exactly j j number of options for j

State transition: As long as the total value of the selected coins does not exceed the target value, you can select k k k th i i i items. both satisfied j ≥ k q ( i − 1 ) j \ge k q(i-1) j≥kq(i−1), can be obtained from f ( i − 1 , j − k q ( i − 1 ) ) f(i - 1, j - kq(i-1)) f(i−1,j−kq(i−1)) shift. k ≥ 0 k \ge 0 k≥0

code

class Solution {
    public int change(int x, int[] q) {
        int n = q.length;
        int[][] f = new int[n + 1][x + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                for (int k = 0; j >= k * q[i - 1]; k++) {
                    f[i][j] += f[i - 1][j - k * q[i - 1]];
                }
            }
        }
        return f[n][x];
    }
}

optimization

formula equivalent deformation

  1. f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − q ( i − 1 ) ) + f ( i − 1 , j − 2 q ( i − 1 ) ) + . . . f(i,j)=f(i-1,j) + f(i-1,j-q(i-1)) + f(i-1,j-2q(i-1)) + ... f(i,j)=f(i−1,j)+f(i−1,j−q(i−1))+f(i−1,j−2q(i−1))+...

  2. f ( i , j − q ( i − 1 ) ) = f ( i − 1 , j − q ( i − 1 ) ) + f ( i − 1 , j − 2 q ( i − 1 ) ) + . . . f(i,j-q(i-1)) = f(i-1,j-q(i-1)) + f(i-1,j-2q(i-1)) + ... f(i,j−q(i−1))=f(i−1,j−q(i−1))+f(i−1,j−2q(i−1))+...

Comparing 1 and 2, it is found that 1 is the same as 2 from the second term, so there is f ( i , j ) = f ( i − 1 , j ) + f ( i , j − q ( i − 1 ) ) f(i,j) = f(i-1,j) + f(i,j-q(i-1)) f(i,j)=f(i−1,j)+f(i,j−q(i−1))

class Solution {
    public int change(int x, int[] q) {
        int n = q.length;
        int[][] f = new int[n + 1][x + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= q[i - 1]) f[i][j] = f[i - 1][j] + f[i][j - q[i - 1]];
                // f[i][j]            = f[i - 1][j] + f[i - 1][j - q[i - 1]] + f[i - 1][j - 2*q[i - 1]] + ...
                // f[i][j - q[i - 1]] =               f[i - 1][j - q[i - 1]] + f[i - 1][j - 2*q[i - 1]] + ...
                // f[i][j] = f[i - 1][j] + f[i][j - q[i - 1]]
            }
        }
        return f[n][x];
    }
}

Optimization space

class Solution {
    public int change(int x, int[] q) {
        int n = q.length;
        // Direct dimensionality reduction
        int[] f = new int[x + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = q[i - 1]; j <= x; j++) {
                f[j] += f[j - q[i - 1]];
            }
        }
        return f[x];
    }
}

Tags: Java Algorithm Dynamic Programming

Posted by adeelahmad on Wed, 18 May 2022 22:07:04 +0300