首页 > 其他分享 >背包问题大合集

背包问题大合集

时间:2024-07-07 10:08:22浏览次数:13  
标签:背包 Scanner int 问题 numItems sc new 合集 dp

dp背包3步曲

1.确定dp[i] [v]的含义(一维的话是dp[v]) :在 0…i 的物品中,体积为 v 的背包中,能够拿到的最大价值为 dp[i] [v]。
2.求关系式
    不拿物品:(物品数量减少)
        一维:dp[v] 
        二维:dp[i] [v] = dp[i-1] [v]
    拿:(物品数量减少,背包体积减物品体积)
        一维:dp[v-weight[i]] 
        二维:dp[i] [v] = dp[i-1] [v-weight[i]]

一维背包:
//遍历物品的数量N
    for (int i = 1; i <= n; i++) {
    //遍历背包的容量V,但是从大到小进行遍历,如果背包容量大于物品体积就拿
        for (int j = capacity; j >= weights[i]; j--) {
            //不拿(背包体积不变)和拿(背包体积减少再加上物品价值),进行比大小,取大值。
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

二维背包:

//遍历物品的数量N

for(int i = 1;i<= n ; i++){
    //遍历背包的容量V
    for(int j = 0; j <= c ; j++ ){
        //如果背包体积小于物品的体积,放不下就不拿了
        if(j<v[i]){
            dp[i][j] = dp[i-1][j];
        }else{
        //不拿(物品数量-1)和拿(物品数量-1,并且背包体积减少再加上物品价值),进行比大小,取大值。
        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    

    }

}

二维背包

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numCases = sc.nextInt();  // Number of test cases

        for (int caseNum = 0; caseNum < numCases; caseNum++) {
            int numItems = sc.nextInt();  // Number of items
            int capacity = sc.nextInt();  // Maximum capacity of the knapsack
            int limit = sc.nextInt();     // Maximum weight limit

            int[] values = new int[numItems + 1];
            int[] weights = new int[numItems + 1];
            int[] profits = new int[numItems + 1];

            for (int i = 1; i <= numItems; i++) {
                values[i] = sc.nextInt();  // Value of the item
                weights[i] = sc.nextInt(); // Weight of the item
                profits[i] = sc.nextInt(); // Profit of the item
            }

            int[][] dp = new int[capacity + 1][limit + 1];  // DP table

            for (int i = 1; i <= numItems; i++) {
                for (int j = capacity; j >= values[i]; j--) {
                    for (int k = limit; k >= weights[i]; k--) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - values[i]][k - weights[i]] + profits[i]);
                    }
                }
            }

            System.out.println(dp[capacity][limit]);
        }

        sc.close();
    }
}



如果每个物品只能用一次,反向更新是必要的;如果每个物品可以用多次,则可以正向更新。

01背包

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numCases = sc.nextInt();  // Number of test cases

        for (int caseNum = 0; caseNum < numCases; caseNum++) {
            int numItems = sc.nextInt();  // Number of items
            int capacity = sc.nextInt();  // Maximum capacity of the knapsack
            int limit = sc.nextInt();     // Maximum weight limit

            int[] values = new int[numItems + 1];
            int[] weights = new int[numItems + 1];
            int[] profits = new int[numItems + 1];

            for (int i = 1; i <= numItems; i++) {
                values[i] = sc.nextInt();  // Value of the item
                weights[i] = sc.nextInt(); // Weight of the item
                profits[i] = sc.nextInt(); // Profit of the item
            }

            int[][] dp = new int[capacity + 1][limit + 1];  // DP table

            for (int i = 1; i <= numItems; i++) {
                for (int j = capacity; j >= values[i]; j--) {
                    for (int k = limit; k >= weights[i]; k--) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - values[i]][k - weights[i]] + profits[i]);
                    }
                }
            }

            System.out.println(dp[capacity][limit]);
        }

        sc.close();
    }
}



多重背包

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

        for (int t = 0; t < nt; t++) {
            int n = sc.nextInt(); // 物品种类
            int c = sc.nextInt(); // 背包容量

            int[] w = new int[n + 1];
            int[] v = new int[n + 1];
            int[] m = new int[n + 1];

            for (int i = 1; i <= n; i++) { // 索引从1开始
                w[i] = sc.nextInt(); // 物品重量
                v[i] = sc.nextInt(); // 物品价值
                m[i] = sc.nextInt(); // 物品个数
            }

            int[] dp = new int[c + 1];

            for (int i = 1; i <= n; i++) {      // 遍历物品
                if (m[i] * w[i] >= c) {         // 如果物品数量无限多(足够多),相当于完全背包
                    for (int j = w[i]; j <= c; j++) {
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                    }
                } else {                                // 如果物品数量有限,先用二进制优化,再当多重背包做,减少循环次数
                    int num = m[i];                       //num表示物品的剩余数量
                    for (int k = 1; num > 0; k <<= 1) {     //k表示当前二进制位的值,当前物品数量>0就说明可以进行二进制优化
                        //取小的,确保每次取的物品数量不超过实际剩余数量,在k变大时,可能会超过num,这时就需要取实际剩余的num而不是k。
                        int cnt = Math.min(k, num);         //cnt表示取出的物品数量
                        num -= cnt;                        //减去已从背包分出去的物品
                        for (int j = c; j >= cnt * w[i]; j--) {
                            dp[j] = Math.max(dp[j], dp[j - cnt * w[i]] + cnt * v[i]);
                        }
                    }
                }
            }

            System.out.println(dp[c]); // 输出结果
        }
        sc.close();
    }
}


最长公共子序列:

import java.util.Scanner;

public class Main {

    static char[] x;
    static char[] y;
    static int[][] dp; // 字符串 X 和字符串 Y 的最长公共子序列的长度。
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        sc.nextLine(); // 吸收换行符
    
        for (int i = 1; i <= t; i++) {
            x = sc.nextLine().toCharArray();
            y = sc.nextLine().toCharArray();
    
            // 初始化dp数组,也就是x,y数组的长度
            int xl = x.length;
            int yl = y.length;
    
            dp = new int[xl + 1][yl + 1]; // 初始化dp数组大小
    
            // 循环数组从1开始,不用加dp[][],因为已经初始化了
            for (int j = 1; j <= xl; j++) { 
                for (int k = 1; k <= yl; k++) {
                    // 如果上一个字符相同,就计算出当前值,更新当前的公共子序列长度
                    if (x[j - 1] == y[k - 1]) {
                        dp[j][k] = dp[j - 1][k - 1] + 1;
                    } else {
                        // 如果不相同,在之前算出来的答案找最适合的,取公共子序列的(二维方向的)前一位进行对比,取大的作为最长公共子序列。
                        dp[j][k] = Math.max(dp[j][k - 1], dp[j - 1][k]);
                    }
                }
            }
            System.out.println(dp[xl][yl]);
        }
    
        sc.close(); // 关闭读写流
    }

}

最长上升子序列:

核心思路:通过动态规划的方法,用 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度,遍历数组,更新每个位置的 dp[i] 值,同时记录整个数组的最长上升子序列长度 maxans

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] numbers = new int[size];
   // 读取输入数组
    for (int i = 0; i < size; i++) {
        numbers[i] = scanner.nextInt();
    }

    int result = lengthOfLIS(numbers);
    System.out.println(result);
}

public static int lengthOfLIS(int[] nums) {
    // dp[i] 表示下标i在 nums[i] 时,也就是0-i的最长上升子序列的长度
    int[] dp = new int[nums.length];
    dp[0] = 1; // 初始化,每个元素自身构成一个长度为 1 的子序列
    int maxans = 1; // 记录最长上升子序列的长度
    //外层循环从1开始遍历每个元素,计算以该元素结尾的最长上升子序列的长度。
    for (int i = 1; i < nums.length; i++) {
        dp[i] = 1; // 也就是初始化dp的每一个元素为1,可以写到外面
        for (int j = 0; j < i; j++) {
        	// 如果 nums[i] 大于 nums[j],则可以将 nums[i] 加入到以 nums[j] 结尾的子序列中
            if (nums[i] > nums[j]) {
                //既然要更新当前下标i位置的最长上升子序列的长度dp,那就是拿上一个已经算出来的值+1更新,当然了要进行对比取最大值,如果当前的dp[i]比dp[j]还大,那就还是使用当前的。
                dp[i] = Math.max(dp[i], dp[j] + 1);		
            }
        }
        // 更新最长上升子序列的长度
        maxans = Math.max(maxans, dp[i]);
    }

    return maxans;
}

超市搞活动(01背包)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getMax(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int knapsack(int capacity, int numItems, int profits[], int weights[]) {
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < numItems; i++) {
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = getMax(dp[j], dp[j - weights[i]] + profits[i]);
        }
    }

    return dp[capacity];
}

int main() {
    int capacity, numItems;

    while (cin >> capacity >> numItems) {
        int profits[numItems], weights[numItems];

        for (int i = 0; i < numItems; i++) {
            cin >> profits[i] >> weights[i];
        }

        int result = knapsack(capacity, numItems, profits, weights);
        cout << result << endl;
    }

    return 0;
}

标签:背包,Scanner,int,问题,numItems,sc,new,合集,dp
From: https://www.cnblogs.com/hanlinyuan/p/18288236

相关文章

  • 启动应用程序出现wevtutil.exe找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个wevtutil.exe文件(挑选合适的版本文件)把它......
  • 启动应用程序出现wininit.exe找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个wininit.exe文件(挑选合适的版本文件)把它放......
  • 【转载】WSL没有eth0 ip问题的共鸣
    看到flyqihua的文章讲了eth0没有ip,深有同感,所以转载文章,以作纪念今天重新安装了wslubuntu系统(不管是哪个版本,我都试过),但是使用ipa的时候就是看不见ip,甚至使用servicenetworkstop,都直接报告没有network服务,折腾了3个小时,最后发现是之前使用过留下的痕迹,在当前用户目录下有个.......
  • P7224 [RC-04] 子集积 (背包 dp + 复杂度优化)
    P7224[RC-04]子集积背包dp+复杂度优化考虑dp。容易想到背包dp,设\(f_{i,j}\)表示考虑了前\(i\)个,当前乘积为\(j\)的方案数。枚举\(a_i\)的倍数转移。复杂度\(O(\sum\limits_{i=1}^n\frac{m}{a_i})\)。如果\(a_i\)互不相同,那么近似于\(O(m\lnm)\)。如果还想......
  • 【AcWing】843. n皇后问题
    剪纸就是判断当前方案一定不合法了就不往下搜了,把这个枝减掉,直接回溯。代码#include<iostream>usingnamespacestd;constintN=10;intn;charg[N][N];//棋盘boolcol[N],dg[N*2],udg[N*2];//分别代表列斜线反斜线有没有占用,对角线个数为2n-1,开2nvoiddfs(......
  • DP:完全背包问题
    文章目录......
  • 遗传算法在选址问题中的应用
    国际期刊InternationalJournalofComplexityinAppliedScienceandTechnology,收录进化计算,机器学习和大数据方面的论文,投稿网址:https://www.inderscience.com/jhome.php?jcode=ijcast 遗传算法(GeneticAlgorithm,GA)是一种基于自然选择和遗传机制的优化算法,适用于解......
  • sizeof 在函数使用中的问题
    使用sizeof来获取数组的大小在某些情况下是可以的,但在涉及到函数参数时可能会有一些问题。使用sizeof获取数组大小当数组在当前作用域内声明时,可以使用sizeof来获取数组的大小。例如:#include<cstdio>intmain(){charbuffer[10];printf("Sizeofb......
  • 2-SAT 问题
    2-SAT问题模型有\(n\)个布尔类型的变量\(x_1,x_2,\ldots,x_n\),有\(m\)条限制形如\(x_i\space[\operatorname{or}/\operatorname{and}]\spacex_j=[1/0]\).求一组符合要求的解。核心问题只需要考虑有没有解。对于每个变量都只有两种取值:\(0/1\),那么把每个变......
  • 06-6.4.2 最短路径问题
    ......