动态规划——01背包和完全背包

• 算法结构

目录

01背包模型

题目 

dp 

 滚动数组优化

第一问 

第二问 

扩展

完全背包

题目 

动态规划​编辑 

滚动数组优化

 关于-1的代码层面优化

💰🪙

背包就是有限制条件的组合问题

01背包模型

题目 

有一个背包能容纳的体积是v，现在有n个物品，第i个物品的体积为vi，价值为wi。

(1)求这个背包至多能装多大价值的物品?

(2) 若背包恰好装满，求至多能装多大价值的物品?

输入描述:

第一行两个整数n和V，表示物品个数和背包体积接下来n行，每行两个数;vi，wi表示第i个物品的体积和价值

1 < n,V,vi,wi < 1000

dp[i][j] 表示从前i个位置选，总体积不超过 j /等于j ，所有选择中，最大的价值。

dp 

import java.util.Scanner;

public class KnapsackProblem {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, V;
        // 物品个数
        n = scanner.nextInt();
        // 背包体积
        V = scanner.nextInt();

        int[] vi = new int[n];
        int[] wi = new int[n];

        for (int i = 0; i < n; i++) {
            // 第 i 个物品的体积
            vi[i] = scanner.nextInt();
            // 第 i 个物品的价值
            wi[i] = scanner.nextInt();
        }

        int maxValue1 = maxValue(vi, wi, V);
        int maxValue2 = maxValueFilled(vi, wi, V);

        System.out.println("问题 1：背包至多能装价值为 " + maxValue1 + " 的物品");
        System.out.println("问题 2：背包恰好装满时，能装价值为 " + maxValue2 + " 的物品");
    }

    public static int maxValue(int[] vi, int[] wi, int V) {
        int n = vi.length;
        int[][] dp = new int[n + 1][V + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (vi[i - 1] <= j) {
                    // 选择放入当前物品和不放入当前物品之间的较大值
                    dp[i][j] = Math.max(dp[i - 1][j], wi[i - 1] + dp[i - 1][j - vi[i - 1]]);
                } else {
                    // 如果当前物品的体积大于背包的剩余容量，则无法放入当前物品，继承之前的最优解
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][V];
    }

    public static int maxValueFilled(int[] vi, int[] wi, int V) {
        int n = vi.length;
        int[][] dp = new int[n + 1][V + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (vi[i - 1] = 0; j--) {
            if (dp[n][j] == dp[n][j]) {
                return dp[n][j];
            }
        }

        return 0;
    }
}

 滚动数组优化

普通的就用两个数组，1推2,1做3；

这里使用一个数组，从右往左计算覆盖。修改j的遍历顺序，去掉所有i动态规划——01背包和完全背包

第一问 

//✅滚动数组
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v=in.nextInt();
        int n=in.nextInt();
        int[] vi=new int[n+1];
        int[] wi=new int[n+1];
        for(int i=1;i<=n;i++){
            vi[i]=in.nextInt();
            wi[i]=in.nextInt();
        }
        int[] dp=new int[v+1];
        for(int i=1;i=vi[i];j--){//从右往左
                
                  dp[j]=Math.max(dp[j],wi[i]+dp[j-vi[i]]);
            }
        }
        System.out.println(dp[v]);
    }
}

//✅原本
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v=in.nextInt();
        int n=in.nextInt();
       
        int[] vi=new int[n+1];
        int[] wi=new int[n+1];
        for(int i=1;i<=n;i++){
            vi[i]=in.nextInt();
            wi[i]=in.nextInt();
        }

        int[][] dp=new int[n+1][v+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j=vi[i])  dp[i][j]=Math.max(dp[i-1][j],wi[i]+dp[i-1][j-vi[i]]);
            }//这里dp[i][j]=Math.max(dp[i][j]也可以
        }
        System.out.println(dp[n][v]);
    }
}

第二问 

       
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();

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

        int[] dp = new int[V + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 1; i = v[i]; j--) {
                if (dp[j - v[i]] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
        }

        System.out.println(dp[V] == -1 ? -1 : dp[V]);
    }
}
//💡原本



     for (int j = 1; j <= V; j++) {
            dp[0][j] = -1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j = v[i] && dp[i - 1][j - v[i]] != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        return dp[n][V]==-1?0:dp[n][V];

扩展

比如目标和，可以思考为一个位置的选与不选。

nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

就可以把数组分成两部分，一部分是a（所有+的和），b（所有-的和的绝对值）假设a>b，有a+b=sum,a-b=target；解出a=（sum+target）/2，即找价值是a….。

//🤑求凑成目标和的方法个数
 总的状态方程dp[i][j] =  dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
dp[0][0]=1

还有一道题按照abcde计算最后结果就是+a-b+d+c-e随便写的，就是在abcde前面加上正号或者负号，想起来 上面的题；那就是把数组分成俩部分，一边是a,一边是b，其中sum=a+b,这道题想让a-b值最小，那就a,b差不多一样大的时候，寻找a=sum/2的背包 。

二维背包问题

dp[i][j][k]表示从前i个字符中选，0的个数不超过m，1的个数不超过n，所有选法中，字符子集的个数。

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len=strs.length;
        int[][][] dp=new int[len+1][m+1][n+1];
        for(int i=1;i<len+1;i++){
            int a=0,b=0;
            for(char ch:strs[i-1].toCharArray()){
                if(ch=='0')a++;
                else b++;
            }
            for(int j=0;j<=m;j++){
                for(int k=0;k=a&&k>=b){
                        dp[i][j][k]=Math.max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
                    }
                }
            }
           
        } 
        return dp[len][m][n];

    }
}

如果给另一个题盈利plan，dp[i][j][k]表示从前i个计划中选，总人数不超过j，总利润至少是k，一共有多少种选法？dp[0][j][0]=1,了解到空集也是一种选法。

dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-g[i][Math.max(0,k-p[i])，其中满足j>=g[i]成立

完全背包

题目 

 描述、

你有一个背包，最多能容纳的体积是V。

现在有n种物品每种物品有任意多个第i种物品的体积为vi,价值为wi。

示例

求这个背包至多能装多大价值的物品?

(2) 若背包恰好装满，求至多能装多大价值的物品?

输入描述:

第一行两个整数n和V，表示物品个数和背包体积接下来n行，每行两个数u;和wi，表示第种物品的体积和价值.1  n,V < 1000

说

输出描述:

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

动态规划动态规划——01背包和完全背包 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = 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();
        }

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

        System.out.println(dp[n][V]);

        int[][] dp2 = new int[n + 1][V + 1];
        for (int j = 1; j <= V; j++) {
            dp2[0][j] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j = v[i] && dp2[i][j - v[i]] != -1) {
                    dp2[i][j] = Math.max(dp2[i][j], dp2[i][j - v[i]] + w[i]);
                }
            }
        }
        int ret = dp2[n][V] == -1 ? 0 : dp2[n][V];
        System.out.println(ret);
    }
}

滚动数组优化

根据dp[i][j]位置的依赖关系判断，j从左往右遍历

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = 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();
        }

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

        System.out.println(dp[V]);

        int[] dp2 = new int[V + 1];
        for (int j = 1; j <= V; j++) {
            dp2[j] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) {
                
                if (dp2[j - v[i]] != -1) {
                    dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
                }
            }
        }
        int ret = dp2[V] == -1 ? 0 : dp2[V];
        System.out.println(ret);
    }
}

 关于-1的代码层面优化

        int[] dp2 = new int[V + 1];
        for (int j = 1; j <= V; j++) {
            dp2[j] = -0x3f3f3f3f;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) {
               
                    dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
                
            }
        }
        int ret = dp2[V]<0 ? 0 : dp2[V];
        System.out.println(ret);

💰🪙

求凑成amount的最少的硬币个数

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;int INF=0x3f3f3f3f;
        //不用Integer.MAX_VALUE因为这个+1——》变小，越界
        int[][] dp=new int[n+1][amount+1];
        for(int j=1;j<=amount;j++) dp[0][j]=INF;
        for(int i=1;i<=n;i++){
            for(int j=0;j=0){
                    dp[i][j]=Math.min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        return dp[n][amount]>=INF?-1:dp[n][amount];//别忘了
    }
}
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;int INF=0x3f3f3f3f;
        //💡不用Integer.MAX_VALUE因为这个+1——》变小，越界
        int[] dp=new int[amount+1];
        for(int j=1;j<=amount;j++) dp[j]=INF;
        for(int i=1;i<=n;i++){
            for(int j=coins[i-1];j=INF?-1:dp[amount];//别忘了
    }
}

凑成面值amount的硬币组合数

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
class Solution {
    public int change(int amount, int[] coins) {
        int n=coins.length;
        int[][] dp=new int[n+1][amount+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j=0)
                    dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/9fdd279c7d.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐