头像

YYC

Coming




离线:6个月前



YYC
9个月前

0-1 背包[二维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]代表第i件物品的价值。
    static int[] w = new int[N];
    // dp[N][N]代表动态规划数组。
    static int[][] dp = new int[N][N];

    public static void main(String... args){
        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        // 读入每件物品的体积和价值,并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (j - v[i] >= 0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);    
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

0-1 背包[一维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]代表第i件物品的体积。
    static int[]  v = new int[N];
    // w[i]代表第i件物品的价值。
    static int[]  w = new int[N];
    // dp[N]代表动态规划数组。
    static int[] dp = new int[N];

    public static void main(String... args){
        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        // 读入每件物品的体积和价值,并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = m; j >= v[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);    
            }
        }
        System.out.println(dp[m]);
    }
}

完全 背包[二维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[] w = new int[N];
    // dp[][] 代表动态规划数组
    static int[][] dp = new int[N][N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        // 读入每件物品的体积和价值,并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (j - v[i] >= 0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);    
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

完全 背包[一维]

import java.util.*;

public class Main{

    static final int N = 1010;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[]  v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[]  w = new int[N];
    // dp[][] 代表动态规划数组
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        // 读入每件物品的体积和价值,并分别存入v和w中。
        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = v[i]; j <= m; j++){
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

多重 背包[二维]

import java.util.*;

public class Main{

    static int N = 110;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[] w = new int[N];
    // s[i]  代表第i件物品的可选数量。
    static int[] s = new int[N];
    // dp[][] 代表动态规划数组
    static int[][] dp = new int[N][N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                for (int k = 0; k <= s[i] && j - k * v[i] >= 0; k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

多重 背包[一维]

import java.util.*;

public class Main{

    static int N = 110;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[]  v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[]  w = new int[N];
    // s[i]  代表第i件物品的可选数量。
    static int[]  s = new int[N];
    // dp[][] 代表动态规划数组
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = m; j >= v[i]; j--){
                for (int k = 0; k <= s[i] && j - k * v[i] >= 0; k++){
                    dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(dp[m]);
    }
}

多重 背包[一维、二进制优化]

import java.util.*;

public class Main{

    static final int N = 12000;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    static int[]  v = new int[N];
    static int[]  w = new int[N];
    static int[]  s = new int[N];
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // Binary optimization
        // 20: 1 2 4 8 + 5
        int cnt = 0;
        for (int i = 1; i <= n; i++){
            // vv 代表第i件物品的体积。
            int vv = sc.nextInt();
            // ww 代表第i件物品的价值。
            int ww = sc.nextInt();
            // ss 代表第i件物品可以使用的最大次数。
            int ss = sc.nextInt();
            int k = 1;
            while (k <= ss){
                cnt++;
                v[cnt] = vv * k;
                w[cnt] = ww * k;
                ss -= k;
                k <<= 1;
            }
            if (ss > 0){
                cnt++;
                v[cnt] = vv * ss;
                w[cnt] = ww * ss;
            }
        }
        n = cnt;

        // 0-1 knapsack
        for (int i = 1; i <= n; i++){
            for (int j = m; j >= v[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

分组 背包[一维]

import java.util.*;

public class Main{

    static final int N = 110;
    static int n = 0;
    static int m = 0;
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];
    static int[]   s = new int[N];
    static int[]  dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            s[i] = sc.nextInt();
            for (int j = 1; j <= s[i]; j++){
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

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

        System.out.println(dp[m]);
    }
}


活动打卡代码 AcWing 9. 分组背包问题

YYC
9个月前
import java.util.*;

public class Main{

    static final int N = 110;
    static int n = 0;
    static int m = 0;
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];
    static int[]   s = new int[N];
    static int[]  dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            s[i] = sc.nextInt();
            for (int j = 1; j <= s[i]; j++){
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

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

        System.out.println(dp[m]);
    }
}


活动打卡代码 AcWing 5. 多重背包问题 II

YYC
9个月前
import java.util.*;

public class Main{

    static final int N = 12000;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    static int[]  v = new int[N];
    static int[]  w = new int[N];
    static int[]  s = new int[N];
    static int[] dp = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // Binary optimization
        // 20: 1 2 4 8 + 5
        int cnt = 0;
        for (int i = 1; i <= n; i++){
            // vv 代表第i件物品的体积。
            int vv = sc.nextInt();
            // ww 代表第i件物品的价值。
            int ww = sc.nextInt();
            // ss 代表第i件物品可以使用的最大次数。
            int ss = sc.nextInt();
            int k = 1;
            while (k <= ss){
                cnt++;
                v[cnt] = vv * k;
                w[cnt] = ww * k;
                ss -= k;
                k <<= 1;
            }
            if (ss > 0){
                cnt++;
                v[cnt] = vv * ss;
                w[cnt] = ww * ss;
            }
        }
        n = cnt;

        // 0-1 knapsack
        for (int i = 1; i <= n; i++){
            for (int j = m; j >= v[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}


活动打卡代码 AcWing 4. 多重背包问题

YYC
9个月前
import java.util.*;

public class Main{

    static int N = 110;
    // n 代表物品的数量。
    static int n = 0;
    // m 代表背包的容量。
    static int m = 0;
    // v[i]  代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[] w = new int[N];
    // s[i]  代表第i件物品的可选数量。
    static int[] s = new int[N];
    // f[][] 代表动态规划数组
    static int[] f = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++){
            for (int j = m; j >= v[i]; j--){
                for (int k = 0; k <= s[i] && j - k * v[i] >= 0; k++){
                    f[j] = Math.max(f[j], f[j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.println(f[m]);
    }
}


活动打卡代码 AcWing 3. 完全背包问题

YYC
9个月前
import java.util.*;

public class Main{

    static final int N = 1010;
    // m 代表物品的数量。
    static int m = 0;
    // n 代表背包的容量。
    static int n = 0;
    // v[i]  代表第i件物品的体积。
    static int[] v = new int[N];
    // w[i]  代表第i件物品的价值。
    static int[] w = new int[N];
    // f[][] 代表动态规划数组
    static int[] f = new int[N];

    public static void main(String... args){

        var sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        // 读入每件物品的体积和价值,并分别存入v和w中。
        for (int i = 1; i <= m; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <= m; i++){
            for (int j = v[i]; j <= n; j++){
                    f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }
        System.out.println(f[n]);
    }
}


活动打卡代码 AcWing 2. 01背包问题

YYC
9个月前
import java.util.*;

public class Main{

    static final int N = 1010;
    // m 代表物品的数量。
    static int m = 0;
    // n 代表背包的容量。
    static int n = 0;
    // v[i]代表第i件物品的体积。
    // w[i]代表第i件物品的价值。
    static int[] v = new int[N];
    static int[] w = new int[N];
    // f[N]代表动态规划数组。
    static int[] f = new int[N];

    public static void main(String... args){
        var sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        for (int i = 1; i <= m; i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        for (int i = 1; i <= m; i++){
            for (int j = n; j >= v[i]; j--){
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);    
            }
        }
        System.out.println(f[n]);
    }
}


活动打卡代码 LeetCode 343. 整数拆分

YYC
9个月前
class Solution {
    public int integerBreak(int n) {
        if (n <= 3) return n - 1;
        int[] nums = {1, 2, 3};
        int l = nums.length;
        var dp = new int[n + 1];
        dp[0] = 1;

        for (int i: nums){
            for (int j = i; j <= n; j++){
                dp[j] = Math.max(dp[j], dp[j - i] * i);
            }
        }
        return dp[n];
    }
}



YYC
9个月前

问题描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

提供给你一些不同面值的硬币,每种硬币均可无限量使用,计算出可凑出金额Amount的最少硬币数量。

举个例子:

Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = [2], amount = 3
Output: -1

Update at 2020_0915

典型的完全背包问题。

先来看下朴素做法:

class Solution {
    public int coinChange(int[] coins, int amount) {

        int l = coins.length;
        var dp = new int[l + 1][amount + 1];

        // 将第一行的所有元素设置为一个较大值,为了后续求Min。
        Arrays.fill(dp[0], amount + 1);

        for (int i = 1; i <= l; i++){
            for (int j = 1; j <= amount; j++){
                // 选择了第i件物品,并求在金额j范围内满足要求的最小数量。
                if (j - coins[i - 1] >= 0){
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                } else {
                // 不选第i件物品。
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // eg. coins = [2], amount = 3
        return dp[l][amount] > amount ? -1 : dp[l][amount];
    }
}

然后对空间进行降维:

class Solution {
    public int coinChange(int[] coins, int amount) {

        int l = coins.length;
        var dp = new int[amount + 1];

        for (int i = 1; i <= amount; i++){
            dp[i] = amount + 1;
        }

        for (int c: coins){
            for (int j = c; j <= amount; j++){
                dp[j] = Math.min(dp[j], dp[j - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

解法1

先看下我最初的实现方法:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];

        for (int i = 1; i <= len; i++){
            for (int j = 1; j <= amount; j++){
                // Bag has rest.
                if (j - coins[i - 1] >= 0){
                    dp[i][j] = dp[i][j - coins[i - 1]] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len][amount];
    }
}

但是当提供硬币无法凑出Amount金额时,就会出现问题。

那么问题到底出在哪里?

我们应该明确定义无法凑出Amount金额这种情况,并将其表示成dp[i][j] = -1

来调整下实现:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        dp[0][0] = 0;

        for (int i = 1; i <= len; i++){
            int min;
            for (int j = 1; j <= amount; j++){
                int coin = coins[i - 1];
                int top  = dp[i - 1][j];
                int jump = dp[i][j - coin];
                // Bag has rest.
                if (j - coin >= 0){
                    if (top == -1 && jump == -1){
                        min = -1;
                    } else if (top == -1){
                        min = jump + 1;
                    } else if (jump == -1){
                        min = top;
                    } else {
                        min = Math.min(top, jump + 1);
                    }
                } else {
                    min = top;
                }
                min = (min == Integer.MAX_VALUE) ? -1 : min;
                dp[i][j] = min;
            }
        }
        return dp[len][amount];
    }
}

还是挺复杂的。

我们调整一下策略,在遍历过程中不处理其最大值,而在最后获取结果的时候再处理:

先来看下示意图:

这里有个小技巧,一开始我们初始化的最大值,可以选择amount + 1,而不是Integer.MAX_VALUE,防止整数溢出。

再考虑下无法凑出Amount金额的场景:

Let's code:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];
        Arrays.fill(dp[0], amount + 1);
        dp[0][0] = 0;

        for (int i = 1; i <= len; i++){
            for (int j = 1; j <= amount; j++){
                int coin = coins[i - 1];
                int top  = dp[i - 1][j];
                // Bag has rest.
                if (j - coin >= 0){
                    dp[i][j] = Math.min(top, dp[i][j - coin] + 1);
                } else {
                    dp[i][j] = top;
                }
            }
        }
        return dp[len][amount] > amount ? -1 : dp[len][amount];

    }
}

老规矩,压缩成一维数组:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= len; i++){
            for (int j = 1; j <= amount; j++){
                int coin = coins[i - 1];
                // Bag has rest.
                if (j - coin >= 0){
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

再来,合并内层循环条件:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int c: coins){
            for (int j = c; j <= amount; j++){
                // Bag has rest.
                dp[j] = Math.min(dp[j], dp[j - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Enjoy it !



活动打卡代码 LeetCode 322. 零钱兑换

YYC
9个月前
class Solution {
    public int coinChange(int[] coins, int amount) {

        int l = coins.length;
        var dp = new int[amount + 1];

        for (int i = 1; i <= amount; i++){
            dp[i] = amount + 1;
        }

        for (int c: coins){
            for (int j = c; j <= amount; j++){
                dp[j] = Math.min(dp[j], dp[j - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}



YYC
9个月前

问题描述

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. 
Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. 
Return the weight of this stone (or 0 if there are no stones left.)

提供一个整数数组,每个元素代表一块石头的重量。

每次从中挑选两块最重的石头然后将其粉碎,假设x <= y,粉碎规则如下:

  • 如果x == y,那么两块石头均被完全粉碎。
  • 如果x != y,那么轻的那块石头x就会被完全粉碎,而重量为y的石头变成y - x

最后,最多会剩下一块石头,请返回其最小重量(如果没有石头剩下,则返回0)。

举个例子:

解法1

Thanks
@rock
@wzc1995

思路是这样的:

使用一个最大堆存储所有元素,然后每次取头两个元素,

若相等,则直接进行下一次遍历,否则将差值(正整数)重新加入最大堆,直至堆中还剩一个元素。

来看下实现:


class Solution {
    public int lastStoneWeight(int[] stones) {

        var maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        for (int s: stones){
            maxHeap.offer(s);
        }

        while (maxHeap.size() > 1){
            int a = maxHeap.poll();
            int b = maxHeap.poll();
            int diff = Math.abs(a - b);
            if (diff > 0){
                maxHeap.offer(diff);
            }
        }
        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

Enjoy it !