动态规划之背包问题

缺乏、安全感 2024-04-01 08:41 69阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

### 算法知识点 ###

> 01背包问题

### 算法题目描述 ###

![在这里插入图片描述][096344f5dac449798e386a4212e149ed.png]

### 做题思路 ###

特点： 每件物品仅用一次

N件物品，容量为V的背包。每件物品只能用一次。

dp\[i\]\[j\]表示所有包含前i个物品且价值和不超过j的所有选法的集合

将fi表示的所有选法分成两大类（划分原则：不漏）

① 选法中不含 i ， 即从 1 ~ i-1中选，且总体积不超过j，即 f\[i-1\]

② 选法中包含 i ，即从 1 ~ i 中选，包含 i，且总体积不超过 j

可以先把第 i 个物品拿出来，即从第 1 ~ i-1中选，且总体积不超过 j-v\[i\]

即：dp\[i-1\]\[j-v\[i\]\] + w\[i\];

所以：dp\[i\]\[j\] = max(dp\[i-1\]\[j\], dp\[i-1\]\[j-v\[i\]\] + w\[i\]);

### 模板代码 ###

import java.util.*;
    public class Main{
        
        public static void main(String[] args){
        
            int N = 1010;
            int[][] dp = new int[N][N];
            int[] v = new int[N];
            int[] w = new int[N];
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int m = scan.nextInt();
            for(int i = 1;i<=n;i++){
        
                v[i]=scan.nextInt();
                w[i]=scan.nextInt();
            }
            for(int i = 1;i<=n;i++){
        
                dp[i][j]=dp[i-1][j];
                if(j>=v[i]) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
    }

> 完全背包问题

在01背包问题的基础上如果使物品的数量有限，就变成了完全背包问题

![在这里插入图片描述][e49c2013883f4bcab3b26b73be6c6d59.png]

分析思路如下  
![在这里插入图片描述][3357eede1a744d3d9a9524371c2f1e91.png]  
再此基础上，我们将dp数组进行改良，为什么可以做类似等差一样的操作，按照正常来说，会比上面多出来一项，因为完全背包问题这里每一种物品是没有数量限制，一直拿到最后一项最多k个满足公式j>=kv，如果拿到k+1个就不满足j>=kv,所以就会跟上面一样项，没有多出来一项，多重背包问题就有数量限制，s个，所以因为拿完s个之后还没有超过总体积的j，所以还有可能多出来一项，s+1则会满足j>=kv的这条公式。

import java.util.*;
    public class Main{
        
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            int N = 1010;
            int[] v = new int[N];
            int[] w = new int[N];
            int[][] f = new int[N][N];
            int n = scan.nextInt();
            int m = scan.nextInt();
            for(int i = 1 ; i <= n ; i ++ ){
        
                v[i] = scan.nextInt();
                w[i] = scan.nextInt();
            }
    
            for(int i = 1 ; i <= n ; i ++ ){
        
                for(int j = 0 ; j <= m ; j ++ ){
        
                    f[i][j] = f[i - 1][j]; // 表示我们划分的第一个不包含i的方案
    
                    // 划分的包含1-k个i的方案,因为可能不存在，所以需要判断一下，v[i]的大小是不是超过总容量j
                    if (j >= v[i]) f[i][j] = Math.max(f[i][j] , f[i][j - v[i]] + w[i]);
                }
            }
            System.out.println(f[n][m]);
        }
    }

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[096344f5dac449798e386a4212e149ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a46859c3db9b4486a7ba51d66f8f0392.png
[e49c2013883f4bcab3b26b73be6c6d59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a791722d7e2d464cb588852a365229ca.png
[3357eede1a744d3d9a9524371c2f1e91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/044fc1819e87415881878d3bca2903aa.png