动态规划——背包问题_c#实现完全背包问题
动态规划问题是一个大家族，作为攻入这个家族的第一部，背包问题无疑成为我们程序爱好者的一开始的绊脚石。那么今天我就再对背包问题的算法进行我的阐述，希望能对大家有所帮助。
这里我先给出我的代码（注：代码的运行结果展示的是动态规划算法背包问题的二维数组形式）
#include using namespace std;int main() { int bag_val; int num; cin>>bag_val>>num; int arr[100][2];//储存物品体积和价值 int dp[100][100];//dp数组 for(int i = 1;i>arr[i][0]>>arr[i][1];}//初始化dp数组for(int i = 0;i<=num;i++){dp[i][0] = 0;} for(int i = 0;i<=bag_val;i++){dp[0][i] = 0;}//判断最优解,如果当前物品值小于背包容量直接继承上一个值for(int i = 1;i<=num;i++){for(int j = 1;jj){dp[i][j] = dp[i-1][j];}else{int o = arr[i][1]+dp[i-1][j-arr[i][0]];dp[i][j] = max(dp[i-1][j],o);}}} //测试for(int i = 0;i<=num;i++){for(int j = 0;j<=bag_val;j++){cout<<dp[i][j]<<\" \";}cout<<endl;} return 0;}那么我们开始分析，首先明确题目：有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是w[i]。求解在放入物品体积小于或等于背包容量的情况下，物品装入背包的价值总和最大，且每件物品只能装入一次。
以下是分别给出的物品体积以及价值：假设背包的容量为6
首先定义背包容量为bag_val，物品个数为num，输入背包容量和物品个数。然后创建一个名为arr的数组储存每个物品的体积和价值，其中每个arr[i]的第0位索引也就是arr[i][0]用来储存体积（充当前面提到的数组c），每个arr[i]的第1位索引也就是arr[i][1]用来储存物品的价值（充当前面提到的数组w）。
再创建名为dp的二维数组用于后续实现动态规划。
代码如下：
int bag_val; int num; cin>>bag_val>>num; int arr[100][2];//储存物品体积和价值 int dp[100][100];//dp数组 for(int i = 1;i>arr[i][0]>>arr[i][1];}背包问题解决的思路如下：
1.将背包容量从0到6作为dp数组的横坐标，将需要选则放置的3个物品作为纵坐标，这里在第一行放置物品0表示没有物品。
2.其中第i行第j列表示背包剩余容量为j-1（因为背包容量从0开始）时装0~物品i-1（同理物品序号从0开始）这几个物品时所能装下的最大价值。例如第1行第1列表示背包剩余容量是0的情况下装0（没有物品）物品时的最大价值，因此等于0；再比如说第4行第3列表示背包剩余容量是3的情况下装0（没有物品）物品、物品1、物品2所能达到的最大价值。
3.初始化dp数组，经过分析可知数组的第一行和第一列元素的值都为0，我们通过代码对其初始化。而之所以要将起始背包容量和起始物品体积设置为0，是为了防止后续操作使得dp数组越界。因此得到：
初始化：
for(int i = 0;i<=num;i++){dp[i][0] = 0;} for(int i = 0;i<=bag_val;i++){dp[0][i] = 0;}4.从第2行2列开始逐行判断，判断逻辑如下：如果当前物品的体积大于这一列所表示的背包容量，那么当前物品一定不能放进背包中，那么当前格子中元素的值就应该继承同列中上一行元素的值，也就是表示在这一列所代表的背包容量下放从0物品到他前一个物品所能容纳物品的最大价值。
当当前物品的体积小于或等于当前背包容量时，需要考虑两种情况。一种是不放入该物品时背包中的物品价值，一种是放入该物品时背包中物品的最大价值。两者作比较，将物品的最大价值填写进当前格子中。
在第二种情况中已经知道要放入物品进背包，所以此时总的物品价值就是已知要放入背包的物品的价值加上背包剩余的容量所能创造的最大价值。
我们从第2行第2列开始看起，此时物品体积为2，小于当前背包容量因此继承同列的上一行元素值，也就是0。接着，第2行第3列。此时物品体积小于背包容量，可以比较两种情况。经过比较可知放入该物品时所能达到的价值最大，因此我们将背包容量为2放物品0和物品1的问题转化为背包容量为2-物品1的体积时放物品0所能达到的最大价值。以此类推：
代码：
for(int i = 1;i<=num;i++){for(int j = 1;jj){dp[i][j] = dp[i-1][j];}else{int o = arr[i][1]+dp[i-1][j-arr[i][0]];dp[i][j] = max(dp[i-1][j],o);}}}5.最后只需要找到表格的最后一行最后一列元素的值，就是本题的答案。
注：本题代码均为c++编写，二位数组空间开辟有限，后续可以自行优化。
