动态规划算法之0-1背包、完全背包、重复背包问题分析

野性酷女 2022-11-29 05:58 215阅读 0赞

### 动态规划 ###

*  0-1背包问题
 *  完全背包问题
 *   *  基于0-1背包
     *  直接计算法（较好）
 *  重复背包问题

# 0-1背包问题 #

假设现在有三件物品：吉他、音响、电脑。  
其重量分别为1Kg、4Kg、3Kg  
其价格是：1500、3000、2000（元）  
***0-1背包问题就是这几种商品的数量都各为 1 个，即每个只有两种选择，是否放入背包。***

![在这里插入图片描述][20200819180153937.png_pic_center]  
0、1背包问题的解决问题是：（填表之后）  
可以得出状态转移方程式：

*  (1)第一行和第一列的值为零
 *  (2)W\[i-1\] > j 时，V\[i\] \[j\] = V\[i-1\] \[j\]
 *  (3) v\[i\]\[j\] = max(v\[i-1\]\[j\], val\[i-1\] + V\[i-1\]\[ j - W\[i-1\]\])

***其中W代表物品的重量， val代表物品的价格，V\[i\]\[j\]代表表格中的数据。因为表格的数据从i = 1,和 j = 1开始， 但是W 和 val是从 0 开始的， 因此需要在程序中将其减去 1 。***

![在这里插入图片描述][20200819164842196.png_pic_center]  
下面看0-1背包问题的代码演示：

#include<iostream>
    #include <vector>
    #include <functional>
    #include <algorithm>
    #include <string>
    #include<map>
    using namespace std;
    /** * 0-1背包问题 */
    int main(int argc,char *agrv[])
    { 
    	// 假设有这几个东西
    	int val[3]{  0 };
    	int weight[3]{  0 };
    	int n = 0;
    	int m = sizeof weight / sizeof(int);
    
    	cout << "请输入物品的价值(3个):";
    	cin >> val[0] >> val[1] >> val[2];
    	cout << "请输入物品的重量:";
    	cin >> weight[0] >> weight[1] >> weight[2];
    	cout << "请输入容器的容量：";
    	cin >> n;
    	int** table = new int*[m + 1];
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		table[i] = new int[n + 1]{ 0};
    	}
    	for (int i = 1; i < m + 1; i++)
    	{ 
    		for (int j = 1; j < n + 1; j++)
    		{ 
    			if (weight[i - 1] > j)
    			{ 
    				table[i][j] = table[i - 1][j];
    			}
    			else { 
    				table[i][j] = max(table[i - 1][j], val[i - 1] +
    					table[i - 1][j - weight[i - 1]]);
    			}
    		}
    	}
    	for (int i = 0; i < m + 1; i ++ )
    	{ 
    		for (int j = 0; j < n + 1; j ++)
    		{ 
    			cout << table[i][j] << " ";
    		}
    		cout << endl;
    	}
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		delete table[i];
    	}
    	delete table;
    	cout<<" Hello... "<<endl;
    	system("pause");
    	return 0;
    }

# 完全背包问题 #

***完全问题就是这几种商品的数量都各为 无数 个，即每个商品可以任意放入背包 无数 次， 只要背包大小可以放的下***  
完全背包问题有两种思考方法：

## 基于0-1背包 ##

（1）基于0-1背包问题，可以选择出放第 i 件商品可以放到所有数量中，进行一一比较来选择出最大价值的需要第 i 件商品的数量。下面看状态转移方程式:  
max(V\[i\]\[j\], k \* Val\[i - 1\] + V\[i - 1\]\[j - K \* W\[i - 1\]\])， 其中 k 的范围是 ***\[0, j / W\[i - 1\]\]*** ，注意都是闭区间。它代表的意思就是所有的可以放入第 i 件商品的范围。下面看代码实现：

#include<iostream>
    #include <vector>
    #include <functional>
    #include <algorithm>
    #include <string>
    #include<map>
    using namespace std;
    /** * 完全背包问题，基于0-1背包问题进行解决 */
    int main(int argc,char *agrv[])
    { 
    	// 假设有这几个东西
    	int val[3]{  0 };
    	int weight[3]{  0 };
    	int n = 0;
    	int m = sizeof weight / sizeof(int);
    
    	cout << "请输入物品的价值(3个):";
    	cin >> val[0] >> val[1] >> val[2];
    	cout << "请输入物品的重量:";
    	cin >> weight[0] >> weight[1] >> weight[2];
    	cout << "请输入容器的容量：";
    	cin >> n;
    	int** table = new int*[m + 1];
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		table[i] = new int[n + 1]{ 0};
    	}
    	for (int i = 1; i < m + 1; i++)
    	{ 
    		for (int j = 1; j < n + 1; j++)
    		{ 
    			for (int k = 0; k <= j / weight[i - 1]; k++)
    			{ 
    				table[i][j] = max(table[i][j], k * val[i - 1] +
    					table[i - 1][j - k * weight[i - 1]]);
    			}
    		}
    	}
    	for (int i = 0; i < m + 1; i ++ )
    	{ 
    		for (int j = 0; j < n + 1; j ++)
    		{ 
    			cout << table[i][j] << " ";
    		}
    		cout << endl;
    	}
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		delete table[i];
    	}
    	delete table;
    	cout<<" Hello... "<<endl;
    	system("pause");
    	return 0;
    }

## 直接计算法（较好） ##

咱们直接看状态转移方程：

*  (1)第一行和第一列的值为零
 *  (2)W\[i-1\] > j 时，V\[i\] \[j\] = V\[i-1\] \[j\]
 *  (3) v\[i\]\[j\] = max(v\[i-1\]\[j\], val\[i-1\] + V\[i\]\[ j - W\[i-1\]\])
 *  注意，上式和0-1背包的状态转移方程只有一处不一致，就是最后采用的是表中同一行的数据，而不是上一行的数据。
 *  **其实这点是比较容易理解的。因为我们现在不在乎有多少数量了，之前算的肯定是最优解。比如，我们现在背包有10Kg的重量，我们放了一个第三件商品（3Kg）之后，剩下的7 Kg我们完全可以从该行的7Kg表中直接查询当时算完的结果就可以了。**

#include<iostream>
    #include <vector>
    #include <functional>
    #include <algorithm>
    #include <string>
    #include<map>
    using namespace std;
    /** * 0-1背包问题 */
    int main(int argc,char *agrv[])
    { 
    	// 假设有这几个东西
    	int val[3]{  0 };
    	int weight[3]{  0 };
    	int n = 0;
    	int m = sizeof weight / sizeof(int);
    
    	cout << "请输入物品的价值(3个):";
    	cin >> val[0] >> val[1] >> val[2];
    	cout << "请输入物品的重量:";
    	cin >> weight[0] >> weight[1] >> weight[2];
    	cout << "请输入容器的容量：";
    	cin >> n;
    	int** table = new int*[m + 1];
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		table[i] = new int[n + 1]{ 0};
    	}
    	for (int i = 1; i < m + 1; i++)
    	{ 
    		for (int j = 1; j < n + 1; j++)
    		{ 
    			if (weight[i - 1] > j)
    			{ 
    				table[i][j] = table[i - 1][j];
    			}
    			else { 
    				table[i][j] = max(table[i - 1][j], val[i - 1] +
    					table[i][j - weight[i - 1]]);
    			}	
    		}
    	}
    	for (int i = 0; i < m + 1; i ++ )
    	{ 
    		for (int j = 0; j < n + 1; j ++)
    		{ 
    			cout << table[i][j] << " ";
    		}
    		cout << endl;
    	}
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		delete table[i];
    	}
    	delete table;
    	cout<<" Hello... "<<endl;
    	system("pause");
    	return 0;
    }

# 重复背包问题 #

**重复背包问题就是多了一个限制条件，该商品的数量不是简单的0-1、无数个。每个商品都规定了一个数量，比如吉他1件、音响3件、电脑2件。**  
重复背包问题其实可以按照完全背包问题的第一种想法来实现，即 k 取值的问题，我们需要将 k 值设为可以放入最大该商品的数量和该商品拥有的数量中较小的那个。下面看状态转移方程式：  
max(V\[i\]\[j\], k \* Val\[i - 1\] + V\[i - 1\]\[j - K \* W\[i - 1\]\])， 其中 k 的范围是 **\[ 0, min(j / W\[i - 1\] , nums\[i - 1\]) \]** ，其中nums代表商品数量数组。注意都是闭区间。它代表的意思就是所有的可以放入第 i 件商品的范围。  
下面看代码：

#include<iostream>
    #include <vector>
    #include <functional>
    #include <algorithm>
    #include <string>
    #include<map>
    using namespace std;
    /** * 0-1背包问题 */
    int main(int argc,char *agrv[])
    { 
    	// 假设有这几个东西
    	int val[3]{  0 };
    	int weight[3]{  0 };
    	int nums[3]{  0 };
    	int n = 0;
    	int m = sizeof weight / sizeof(int);
    
    	cout << "请输入物品的价值(3个):";
    	cin >> val[0] >> val[1] >> val[2];
    	cout << "请输入物品的重量:";
    	cin >> weight[0] >> weight[1] >> weight[2];
    	cout << "请输入容器的容量：";
    	cin >> n;
    	cout << "请输入商品的数量：";
    	cin >> nums[0] >> nums[1] >> nums[2];
    	int** table = new int*[m + 1];
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		table[i] = new int[n + 1]{ 0};
    	}
    	for (int i = 1; i < m + 1; i++)
    	{ 
    		for (int j = 1; j < n + 1; j++)
    		{ 
    			for (int k = 0; k <= min(j / weight[i - 1], nums[i - 1]); k++)
    			{ 
    				table[i][j] = max(table[i - 1][j], k * val[i - 1] +
    					table[i - 1][j - k * weight[i - 1]]);
    			}
    		}
    	}
    	for (int i = 0; i < m + 1; i ++ )
    	{ 
    		for (int j = 0; j < n + 1; j ++)
    		{ 
    			cout << table[i][j] << " ";
    		}
    		cout << endl;
    	}
    	for (int i = 0; i < m + 1; i++)
    	{ 
    		delete table[i];
    	}
    	delete table;
    	cout<<" Hello... "<<endl;
    	system("pause");
    	return 0;
    }

[20200819180153937.png_pic_center]: /images/20221124/e9c49d9c47664da2a876f703eed1ca07.png
[20200819164842196.png_pic_center]: /images/20221124/02bb0de33f124dcc975a50a1fd2c8250.png