背包问题-动态规划

逃离我推掉我的手 2023-08-17 17:42 126阅读 0赞

[背包问题九讲][Link 1]  
[背包问题参考博客][Link 2]

### 文章目录 ###

*   *  介绍:
     *  背包问题
     *   *  01背包问题
         *  完全背包
         *  多重背包
         *  混合背包
         *  二维费用背包
         *  分组背包
         *  有依赖的背包

## 介绍: ##

背包问题：有一系列的物品，每个物品有自己的**价值v**和**重量w**，怎么选取物品放到有一定**最大承受重量m**的背包里面达到**价值最大**的问题。

1.  如果每件物品只有一件：**01背包**
2.  如果每件物品可以拿无数次：**完全背包**
3.  如果第 i 种商品有 n 件：**多重背包**
4.  如果将01背包、完全背包、多重背包混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）: **混合背包**
5.  **二维费用背包问题**
6.  **分组背包问题**
7.  **有依赖的背包问题**

## 背包问题 ##

### 01背包问题 ###

*  问题描述：一共有 i 种商品，每种商品的价值和重量是 v\[i\] w\[i\]，怎么选取放到总容量是M的背包中以达到最大价值，每种商品只有一个。
 *  问题解答思路：

假设  f \[ i , m \] f \[ i , m \] f\[i,m\] 就设为从**前 i 种物品**中选择放入**当前容量为 m** 的背包**最大的价值**。那么状态转移方程为：  
 f \[ i , m \] = m a x \{ f \[ i − 1 , m \] ,    f \[ i − 1 , m − w \[ i \] \] + v \[ i \] \} f \[ i , m \]=max \\left \\\{ f\[i-1,m\], \\space \\space f\[i-1,m-w\[i\]\]+v\[i\] \\right \\\} f\[i,m\]=max\{ f\[i−1,m\],  f\[i−1,m−w\[i\]\]\+v\[i\]\}  
解释：考虑子问题，将第i种商品放入背包：  
   自顶向下的思路   ： f \[ i , m \] = \{ f \[ i − 1 , m \] ：第i种物品不放 f \[ i − 1 , m − w \[ i \] \] + v \[ i \] ：放第i种物品 \\textbf\{ 自顶向下的思路 \}： f\[i,m\]=\\left\\\{ \\begin\{aligned\} &f\[i-1, m\] \\text\{：第i种物品不放\}\\\\ & f\[i-1,m-w\[i\]\]+v\[i\] \\text\{：放第i种物品\} \\end\{aligned\} \\right.  自顶向下的思路 ：f\[i,m\]=\{ f\[i−1,m\]：第i种物品不放f\[i−1,m−w\[i\]\]\+v\[i\]：放第i种物品  
如果第 i 种商品不放，那么最大价值就等于将前i-1种商品放入 容量为 m的背包；如果放第 i 种物品(前提是当前容量m > w\[i\])，则最大价值：将前 i-1 种商品放到 容量为 m-w\[i\]的最大价值+当前的v\[i\]

*  例子：

背包的容量 M= 8

示例代码：

int main(int argc, char* argv[])
    { 
        int w[5] = { 0, 2, 3, 4, 5};
        int v[5] = { 0, 3, 4, 5, 6};
        int M = 8;
        int dp[5][9];
        memset(dp, 0, sizeof(dp));
    
        for(int i=1; i<=4; i++) // 四种商品
        { 
    		for(int j=1; j<=M; j++) //包的容量
    		{ 
    		    if(j<w[i]) // 当前的容量 < 当前的物品重量
    				dp[i][j] = dp[i-1][j]; // 不放当前第 i 种商品 
    		    else // 放第i种商品，取放与不放的最大值
    				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
    		}
        }
    
        // 输出动态规划表
        for (int i = 0; i < 5; i++) 
        { 
    		for (int j = 0; j < 9; j++) 
    		{ 
    		    cout << dp[i][j] << ' ';
    		}
    		cout << endl;
        }
    
        return 0;
    }

结果：4种商品，背包容量8的最优解是：10  
![在这里插入图片描述][20191002110937427.png]

*  空间复杂度的优化  
    有n种商品，背包容量为M，以上方法的时间和空间复杂度均为O(NM)，时间复杂度没法优化，但是空间复杂度依然可以优化到O(M)，实际可以用一维数组 dp\[m+1\] 即可。外层循环的每次 i 初始值是上一轮递推得到的值（i - 1时的情况），需要注意的是我们必须**倒序跟新**, 这样才能保证推dp\[j\]时dp\[j-w\[i\]\]保存的是状态dp\[i-1\]\[j-w\[i\]\] 的值，这样符合状态转移方程

int main(int argc, char* argv[])
    { 
        int w[5] = { 0, 2, 3, 4, 5};
        int v[5] = { 0, 3, 4, 5, 6};
        int M = 8;
        int dp[9];
        memset(dp, 0, sizeof(dp));
    
        for(int i=1; i<=4; i++) // 四种商品
        { 
    		for(int j=M; j>0; j--) //包的容量
    		{ 
    		    if(j>=w[i]) // 当前的容量 >= 当前的物品重量
    			dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    		}
        }
    
        // 输出动态规划表
        for (int j = 0; j < 9; j++) 
        { 
    		cout << dp[j] << ' ';
        }
    
        return 0;
    }

结果：  
![在这里插入图片描述][20191002114512999.png]

*  01背包拓展：

1.  求取的不是价值的最大值而是最小值：把max换成min即可，原理相同。
2.  求最优解有哪些物品：[背包问题最优解回溯][Link 3]
3.  要求“恰好装满背包”时的最优解[背包九讲的01背包-初始化细节问题][Link 1]，[例子][Link 4]，可以初始化 -999，有可能最后没有满足要求的方案，非法值就是 **-大数**
4.  如果碰到物品的v\[i\]是带有负数或者小数，动态规划的数组申请为1维的，如果连重量w\[i\]是小数，申请为1维的动态规划的数组也不满足要求，因为小数没办法作为数组的下标：上面代码的 dp\[j-w\[i\]\]，我们可以选择将背包容量和每个物品的重量同时乘以大数满足整数要求。

--------------------

### 完全背包 ###

*  问题描述：有N种物品和一个容量为M的背包，每种物品都有无限件可用。第i种物品的重量是w\[i\]，价值是v\[i\]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。  
      
    
 *  问题解答思路：在选取第 i 种商品的时候，可以选 0, 1, 2 … n , 只要保证 n个商品的重量 <= 当前背包能承受的重量，所以按照01背包的假设：F\[i\]\[m\]代表前i种商品放到容量m的背包中的最大价值，那么状态转移方程：  
     f \[ i \] \[ m \] = m a x \{ f \[ i − 1 \] \[ m − k ∗ w \[ i \] \] + k ∗ v \[ i \] \}        k ∗ w \[ i \] < = m f\[i\]\[m\] = max \\left \\\{ f\[i-1\]\[m-k\*w\[i\]\] +k\*v\[i\]\\right \\\} \\space \\space \\space \\space \\space \\space k\*w\[i\]<=m f\[i\]\[m\]=max\{ f\[i−1\]\[m−k∗w\[i\]\]\+k∗v\[i\]\}      k∗w\[i\]<=m  
    k代表选几个第i种商品，当k =0 时相当于不选，最大价值等于f\[i-1\]\[m\]。
 *  示例代码

int w[3] = { 0, 5, 7}; // 每种商品重量：第一个初始化为0，2种商品
    int v[3] = { 0, 5, 8}; // 每种商品价值：第一个初始化为0，2种商品
    int M = 10; //背包容量
    int dp[3][11]; //一定要3行，否则计算第一行的时候 dp[i-1][]会越界
    
    void DP(void)
    { 
    	for (int i = 1; i <= 2; i++)
    	{ 
    		for (int j = 1; j <= M; j++)
    		{ 
    			for (int k = 0; k * w[i] <= j; k++)
    			{ 
    				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
    			}
    		}
    	}
    }
    
    int main(int argc, char *argv[])
    { 
    	DP();
    
    	for (int i = 1; i < 3; i++) //输出有用2行
    	{ 
    		for (int j = 1; j < 11; j++)
    		{ 
    			cout << dp[i][j] << " ";
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

结果：动态规划表：  
![在这里插入图片描述][20191004105708762.png]

*  代码优化  
    上面的代码和01背包一样需要求 N\*M个状态，但是求每个状态的时间已经不是常数了，是：m/w\[i\]，有可能m/w\[i\] = m，所以最坏的时间复杂度是O( N M 2 NM^2 NM2)，空间复杂度O(NM)
 *  空间复杂度优化：从O(NM)->O(M)

int w[3] = { 0, 5, 7}; // 第一个为 0
    int v[3] = { 0, 5, 8};
    int M = 10;
    int dp[11]; 
    
    void DP(void)
    { 
    
    	for (int i = 1; i <= 2; i++)
    	{ 
    		for (int j = M; j >= w[i]; j--)
    		{ 
    			for (int k = 0; k * w[i] <= j; k++)
    			{ 
    				dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
    			}
    		}
    	}
    }
    
    int main(int argc, char *argv[])
    { 
    	DP();
    
    	for (int j = 1; j < 11; j++)
    	{ 
    		cout << dp[j] << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

*  时间复杂度的优化O( N M 2 NM^2 NM2)->O(NM)  
    我们没有必要对每个 m 都去计算到底最多放几个物品，比如说 放 第 i个物品，放2个是从放1个+v\[i\]得到的，放3个是从放两个的价值上+v\[i\]得到的，转换成公式： f \[ i \] \[ m \] = m a x \{ f \[ i − 1 \] \[ m \] , f \[ i \] \[ m − w \[ i \] \] + v \[ i \] \} f\[i\]\[m\] =max \\left \\\{ f\[i-1\]\[m\],f\[i\]\[m-w\[i\]\] +v\[i\]\\right \\\} f\[i\]\[m\]=max\{ f\[i−1\]\[m\],f\[i\]\[m−w\[i\]\]\+v\[i\]\}  
    要么第i种商品不选， f \[ i \] \[ m \] = f \[ i − 1 \] \[ m \] f\[i\]\[m\] =f\[i-1\]\[m\] f\[i\]\[m\]=f\[i−1\]\[m\]，要么从现有的i种物品的个数上+1： f \[ i \] \[ m − w \[ i \] \] + v \[ i \] f\[i\]\[m-w\[i\]\] +v\[i\] f\[i\]\[m−w\[i\]\]\+v\[i\]，再比较谁的价值大

int w[3] = { 0, 5, 7}; // 第一个为 0
    int v[3] = { 0, 5, 8};
    int M = 10;
    int dp[11]; 
    
    void DP(void)
    { 
    
    	for (int i = 1; i <= 2; i++)
    	{ 
    		for (int j = 1; j <= M; j++)
    		{ 	
    			if(j>=w[i])	//从原来的基础上再加一个 第i种 商品 
    				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    			else
    				dp[j] = dp[j]; // j<=w[i]的时候，dp[j]存的是i-1时刻的dp[j],相当于第i种商品不选
    			
    		}
    	}
    }
    
    int main(int argc, char *argv[])
    { 
    	DP();
    
    	for (int j = 1; j < 11; j++)
    	{ 
    		cout << dp[j] << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

为什么完全背包从 1->M遍历，而01背包从M->1遍历。

1.  0-1背包从m->1遍历是因为，f\[i\]\[m\] = f\[i-1\]\[m\] 或者 f\[i-1\]\[m-w\[i\]\]+v\[i\]，一维数组里面存的就是上次的f\[i-1\]，如果从1->m遍历会**先**得到当前i的值，就会覆盖i-1时刻的值，然而一维数组后面的值是由i-1时刻前面的值得到，但是已经被覆盖了。
2.  完全背包时间复杂度为O(NM)的解法，从1->m遍历是因为，开始遍历的时候一维数组里面存的也是上次f\[i-1\]的值，在m<w\[i\]的时候直接取f\[i-1\]，但是当m>=w\[i\]的时候，f\[i\]取的是当前i取了k-1次结果再加上一个i种物品的结果：f\[i\]\[m\]= f\[i\]\[m-w\[i\]\]+v\[i\]，和i-1时候的值没有关系，所以需要从1->m进行遍历

--------------------

### 多重背包 ###

*  问题描述：有N种物品和一个容量为M的背包，每种物品上限n\[i\]件可选。第i种物品的重量是w\[i\]，价值是v\[i\]。求解物品怎么装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。  
      
    
 *  问题解答思路：

1.  每次在选第 i 种物品的时候，可以有n\[i\]+1种选择：0，1，… ，n\[i\]+1。令f\[i\]\[m\]表示前i种物品恰放入一个容量为m的背包的最大权值，则状态转移方程： f \[ i \] \[ m \] = m a x \{ f \[ i − 1 \] \[ m − k ∗ w \[ i \] \] + k ∗ v \[ i \]      ∣   0 < = k < = n \[ i \] ,    k ∗ w \[ i \] < = m \} f\[i\]\[m\]=max\\left \\\{f\[i-1\]\[m-k\*w\[i\]\]+k\*v\[i\]\\space\\space\\space\\space|\\space 0<=k<=n\[i\] , \\space\\space k\*w\[i\]<=m\\right \\\} f\[i\]\[m\]=max\{ f\[i−1\]\[m−k∗w\[i\]\]\+k∗v\[i\]    ∣ 0<=k<=n\[i\],  k∗w\[i\]<=m\}  
    这样的**时间复杂度为：** O ( M ∗ ∑ n \[ i \] ) O(M\*\\sum n\[i\]) O(M∗∑n\[i\])  
      
    
2.  还可以将每种物品看成n\[i\]种不同的商品，只不过每个商品的价值v\[i\]和重量w\[i\]都是一样的，这样就转化成有  ∑ n \[ i \] \\sum n\[i\] ∑n\[i\] 种物品的01背包问题，但是时间复杂度依然是: O ( M ∗ ∑ n \[ i \] ) O(M\*\\sum n\[i\]) O(M∗∑n\[i\])

*  时间复杂度优化： O ( M ∗ ∑ n \[ i \] ) O(M\*\\sum n\[i\]) O(M∗∑n\[i\]) \->  O ( M ∗ ∑ log ⁡ n \[ i \] ) O(M\*\\sum \\log n\[i\]) O(M∗∑logn\[i\])  
      我们能不能将n\[i\]个物品转化成更少的物品，用这些更少的物品代替n\[i\]个物品，这些物品的随意组合都能得到原来从0…n\[i\]种选择，这样减少物品选择的可能。  
      根据二进制数的原理，每个数都是有1,2,4…组成，所以将n\[i\]分成1,2,4… 2 k − 1 , n \[ i \] − 2 k + 1 2^\{k-1\},n\[i\]-2^\{k\}+1 2k−1,n\[i\]−2k\+1，且k是满足： n \[ i \] − 2 k + 1 > 0 n\[i\]-2^k+1>0 n\[i\]−2k\+1>0的最大整数。  
      举个例子, n\[i\] = 13，满足 n \[ i \] − 2 k + 1 > 0 n\[i\]-2^k+1>0 n\[i\]−2k\+1>0的最大整数的k =3，则n\[i\]分解成 1,2, 4, 6；n\[i\]小于 2 k 2^\{k\} 2k的部分都能由 1,2,4组成(二进制的第0,1,2位，最大构成7，能组成0- 2 k − 1 2^\{k\}-1 2k−1)，大于等于 2 k 2^\{k\} 2k的部分可以由最后一个数 n \[ i \] − 2 k + 1 n\[i\]-2^k+1 n\[i\]−2k\+1=6和前面的1,2,4组合而成。最大组合成n\[i\]满足了多重背包的约束条件。  
    最后将13个第i种物品拆成 1×i，2×i，4×i，6×i，他们的价值和重量分别也得乘以系数，时间复杂度成了 O ( M ∗ ∑ log ⁡ n \[ i \] ) O(M\*\\sum \\log n\[i\]) O(M∗∑logn\[i\])  
    [基于单调队列的O(NM)的时间复杂度优化][O_NM]
 *  代码示例  
    ![在这里插入图片描述][2019100511042915.png]

1.  填表  
    ![在这里插入图片描述][20191005122719955.png]
2.  递归解法

int w[4] = { 0, 3, 4, 5}; // 重量 第一个为 0
    int v[4] = { 0, 2, 3, 4}; //价值
    int n[4] = { 0, 4, 3, 2}; //数量
    
    int DP(int i, int m) //前i种商品放入容量为m的背包中
    { 
        int result = 0;
        if(i==0 || m==0) result = 0;
        else if(w[i] > m)
        { 
    		result = DP(i-1, m);
        }
        else
        { 
    		for(int k=0; k<=n[i] && k*w[i] <= m; k++) //对比完全背包，多了 k<=n[i]的数量判断
    		{ 
    		    int tmp = DP(i-1, m-w[i]*k)+v[i]*k;
    		    if(tmp > result)
    		    { 
    				result = tmp;
    		    }
    		}
        }
        return result;
    }
    
    int main(int argc, char *argv[])
    { 
    	cout << DP(3, 15); // 结果: 11
    }

1.  动态规划

int w[4] = { 0, 3, 4, 5}; // 第一个为 0
    int v[4] = { 0, 2, 3, 4};
    int n[4] = { 0, 4, 3, 2};
    int M = 15;
    
    void DP_2D(void)
    { 
    	int dp[4][16]; 
    	memset(dp, 0, sizeof(dp));
    
        for(int i=1; i<=3; i++) // 3件物品
        { 
    		for(int m=1; m<=M; m++)
    		{ 
    		    for(int k=0; k*w[i]<=m && k<=n[i]; k++) //加了判断条件 k<=n[i]
    		    { 
    				dp[i][m] = max(dp[i][m], dp[i-1][m-k*w[i]]+k*v[i]);
    		    }			 
    		}
        }
        
        //输出动态规划表
        for(int i=0; i<4; i++)
        { 
    		for(int j=0; j<=M; j++)
            { 
    	   		cout << dp[i][j] << " ";
            } 
    		cout << endl;
        }
    }
    
    void DP_1D(void) // 
    { 
        int dp[M+1];
        memset(dp, 0, sizeof(dp));
    
        for(int i=1; i<=3; i++)
        { 
    		for(int m=M; m>=w[i]; m--) // 逆序计算
    		{ 
    			int k = 1;
    			while(k*w[i] <= m && k <= n[i])
    			{ 
    				dp[m] = max(dp[m], dp[m-k*w[i]]+k*v[i]);
    				k++;
    			}				
    		}
        }
    
        for(int i=0; i<=M; i++)
        { 
           cout << dp[i] << " ";
        }
    }
    
    
    void DP_01(void)//转成01背包
    { 
    	int dp[M+1];
        memset(dp, 0, sizeof(dp));
    
        for(int i=1; i<=3; i++)
        { 
    		for(int l=1; l<=n[i]; l++)
    		{ 
    			for(int m=M; m>=w[i]; m--)
    			{ 	
    					dp[m] = max(dp[m], dp[m-w[i]]+v[i]);
    			}
    		}
        }
    
    
        for(int i=0; i<=M; i++)
        { 
           cout << dp[i] << " ";
        }
    }
    
    
    //时间复杂度优化为 M*sum(log n[i])的解法
    void DP_MlogN()
    { 
        int dp[M+1];
        int new_w[4]; //二进制分解之后的物品重量，取物品中最大的数量 
        int new_v[4];//二进制分解之后的物品价值
        int tol = 0; // 二进制分解之后的个数
        memset(dp, 0, sizeof(dp));
    
    	
        for(int i=1; i<=3; i++)
        { 
    		for(int j=1; j<=n[i]; j<<=1) //每遍历一个物品，进行分解
    		{ 
    		    n[i] -= j;
    		    new_w[++tol] = j*w[i];
    		    new_v[tol] = j*v[i];
    		}
    		if(n[i])
    		{ 
    		    new_w[++tol] = n[i]*w[i];
    		    new_v[tol] = n[i]*v[i];
    		    n[i] = 0;
    		}
    		// ---------至此分解完成
    		for(int x=1; x<=tol; x++) //利用分解完的物品进行01背包处理, 计算时间复杂度上面一层相对于这两层忽略
    		for(int m = M; m>new_w[x]; m--)
    		{ 
    	
    		    dp[m] = max(dp[m], dp[m-new_w[x]]+new_v[x]);
    		}
        }
    
    
    
    
        for(int i=0; i<=M; i++)
        { 
           cout << dp[i] << " ";
        }
    
    
    }
    
    
    void DP_MN() //使用单调队列实现时间复杂度是 O(MN)
    { 
    
    
    }
    
    
    int main(int argc, char *argv[])
    {    
        //DP_2D();
    	//DP_1D();
    	//DP_01();
    	DP_MlogN();
    	//DP_MN();
        return 0;
    }

--------------------

### 混合背包 ###

*  问题描述：有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包），每种物品有自己价格v\[i\] 和 重量 w\[i\] ，背包容量M，如何选择物品达到最大值？
 *  问题解答思路：只要在物品循环的一层判断当前物品属于哪种，再应用哪种的状态方程即可。
 *  时间复杂度：因为每种问题都有O(MN)的解法，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。
 *  代码示例：  
    ![在这里插入图片描述][20191006104201850.png]

#include <iostream>
    #include <string.h>
    
    
    using namespace std;
    
    int w[4] = { 0, 2, 3, 4}; //重量 第一个为 0 
    int v[4] = { 0, 1, 3, 5}; // 价值
    int n[4] = { 0, 0, 1, 4}; // 个数 ，0 代表无穷多个
    int M = 10; 
    
    
    void DP(void)
    { 
        int dp[M+1];
        memset(dp, 0, sizeof(dp));
    
    
        for(int i=1; i<=3; i++)
        { 
            if(n[i] == 0) //完全背包
            { 
                for(int j=w[i]; j<=M; j++)
                { 
                    dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
                }
            }
            else if(n[i] == 1) // 01背包
            { 
                for(int j=M; j>=w[i]; j--)
                { 
                    dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
                }
            }
            else //多重背包
            { 
                for(int j=M; j>=w[i]; j--)
                { 
                    int k=1; 
                    while(k*w[i]<=j && k<=n[i])
                    { 
                        dp[j]= max(dp[j], dp[j-k*w[i]]+k*v[i]);
                        k++;
                    }
                }
            }
        }
    
    
        //输出结果
        for(int i=1; i<=M; i++)
        { 
           cout << dp[i] << " ";
        }
    }
    
    
    
    
    int main(int argc, char *argv[])
    {    
        DP();  
        return 0;
    }

输出结果和上面表算的最后一行是一样的：  
![在这里插入图片描述][20191006110133444.png]

--------------------

### 二维费用背包 ###

*  问题描述：  
      
    
 *  问题解答思路：

--------------------

### 分组背包 ###

*  问题描述：有N件物品和一个容量为M的背包。第i件物品的重量是w\[i\]，价值是v\[i\]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

*  问题解答思路：在每组的物品中可以选择其中一种或者不选，假设f\[k\]\[m\]表示前k组放入容量m背包的最优结果。  
     f \[ k \] \[ m \] = m a x \{ f \[ k − 1 \] \[ m \] , f \[ k − 1 \] \[ m − w \[ i \] \] + v \[ i \]    ∣ 物 品 i 属 于 组 k \} f\[k\]\[m\]=max \\left \\\{ f\[k-1\]\[m\],f\[k-1\]\[m-w\[i\]\]+v\[i\]\\space\\space|物品i属于组k \\right \\\} f\[k\]\[m\]=max\{ f\[k−1\]\[m\],f\[k−1\]\[m−w\[i\]\]\+v\[i\]  ∣物品i属于组k\}  
    伪代码：

for 所有的组k
        for m=M..0
            for 所有的i属于组k
                f[m]=max{ f[m],f[m-w[i]]+v[i]}

*  代码示例：

盗来的图  
![在这里插入图片描述][20191007110035350.png]  
![在这里插入图片描述][20191007110821256.png]

#include <iostream>
    #include <string.h>
    using namespace std;
    
    int M = 10; // 总背包容量
    
    // 3组每组2种商品,商品的总量和价值如下
    int w[4][3] ={ { 0,0,0},{ 0,2,3},{ 0,4,5},{ 0,2,1}};  // 重量
    int v[4][3] ={ { 0,0,0},{ 0,1,2},{ 0,2,3},{ 0,4,3}};  //价值
    
    
    
    void DP()
    { 
        int dp[M+1];
        memset(dp, 0, sizeof(dp));
    
        for(int k=1; k<=3; k++) //3组
        { 
    		for(int m=M; m>0; m--) // 
    		{ 
    		    for(int i=1; i<=2; i++) //每组里面的物品
    		    { 
    				if(m>=w[k][i])
    				    dp[m] = max(dp[m], dp[m-w[k][i]]+v[k][i]);
    		    }
    		}
        }
    
        
    //输出结果
        for(int i=1; i<=M; i++)
    		cout << dp[i] << " ";
        cout << endl;
    }
    
    
    
    
    int main(int argc, char *argv[])
    {    
       
        DP();
        
        return 0;
    }

--------------------

### 有依赖的背包 ###

[Link 1]: https://www.kancloud.cn/kancloud/pack/70125
[Link 2]: https://www.cnblogs.com/-guz/p/9866118.html
[20191002110937427.png]: /images/20230808/54865b75f191436aa22bdb83ee1d0239.png
[20191002114512999.png]: /images/20230808/3f7458ab6ccd4acca9c2c104ad8a5619.png
[Link 3]: https://blog.csdn.net/qq_38410730/article/details/81667885
[Link 4]: https://www.cnblogs.com/buddho/p/7867920.html
[20191004105708762.png]: /images/20230808/a3e74f64d4c74d49b30627928f6755b3.png
[O_NM]: https://blog.csdn.net/qq_40679299/article/details/81978770
[2019100511042915.png]: /images/20230808/e7e20cfb4cbc4ac38ffed9259a6745f6.png
[20191005122719955.png]: /images/20230808/6696fc866b0e467a868617dfbc1cbe10.png
[20191006104201850.png]: /images/20230808/b795f62b0d274b0d8df695b5aa1a8703.png
[20191006110133444.png]: /images/20230808/9c6a3542111c4f368a03bb1d32fe96e5.png
[20191007110035350.png]: /images/20230808/1b59f02c671648c5a17a058e6fec827d.png
[20191007110821256.png]: /images/20230808/38afbc96530b482fad178feea534f446.png