深圳商城网站设计推荐,设计色彩的门户网站模板,oss如何做网站,网站微信建设方案背包问题的解决过程
在解决问题之前#xff0c;为描述方便#xff0c;首先定义一些变量#xff1a;Vi表示第 i 个物品的价值#xff0c;Wi表示第 i 个物品的体积#xff0c;定义V(i,j)#xff1a;当前背包容量 j#xff0c;前 i 个物品最佳组合对应的价值#xff0c;同…背包问题的解决过程
在解决问题之前为描述方便首先定义一些变量Vi表示第 i 个物品的价值Wi表示第 i 个物品的体积定义V(i,j)当前背包容量 j前 i 个物品最佳组合对应的价值同时背包问题抽象化X1X2…Xn其中 Xi 取0或1表示第 i 个物品选或不选。
1、建立模型即求max(V1X1V2X2…VnXn)
2、寻找约束条件W1X1W2X2…WnXncapacity
3、寻找递推关系式面对当前商品有两种可能性
包的容量比该商品体积小装不下此时的价值与前i-1个的价值是一样的即V(i,j)V(i-1,j)
还有足够的容量可以装该商品但装了也不一定达到当前最优价值所以在装与不装之间选择最优的一个即V(i,j)maxV(i-1,j)V(i-1,j-w(i))v(i)。
其中V(i-1,j)表示不装V(i-1,j-w(i))v(i) 表示装了第i个商品背包容量减少w(i)但价值增加了v(i)
由此可以得出递推关系式
jw(i) V(i,j)V(i-1,j)
jw(i) V(i,j)maxV(i-1,j)V(i-1,j-w(i))v(i) #include stdio.h
int main() { // 定义数组a用于存储每个节点的权值数组b作为邻接矩阵存储节点间的连接关系 // dp数组用于存储从每个节点出发能得到的最大权值和d数组用于记录路径 int a[30], b[30][30] {0}, n, dp[30] {0}, d[30] {0}; // 读取节点的数量n scanf(%d, n); // 读取每个节点的权值存储到数组a中这里从a[1]到a[n]存储有效数据 for (int i 1; i n; i) scanf(%d, a[i]); // 读取邻接矩阵b的上三角部分表示节点之间的连接关系 // b[i][j]为1表示节点i到节点j有一条边 for (int i 1; i n; i) { for (int j i 1; j n; j) { scanf(%d, b[i][j]); } } // 初始化dp[n]为节点n的权值因为从节点n出发没有后续节点所以它的最大权值和就是自身权值 dp[n] a[n]; // 记录当前最大权值和对应的节点编号初始化为n int maxi n; // 从倒数第二个节点开始向前遍历计算从每个节点出发的最大权值和 for (int i n - 1; i 1; i--) { // 初始化dp[i]为节点i的权值 dp[i] a[i]; // 初始化d[i]为0表示当前还没有找到后续能使权值和更大的节点 d[i] 0; // 遍历节点i之后的所有节点j寻找从节点i到节点j的路径 for (int j i 1; j n; j) { // 如果节点i到节点j有边并且通过节点j能使从节点i出发的权值和更大 if (b[i][j] 1 dp[j] a[i] dp[i]) { // 更新从节点i出发的最大权值和 dp[i] dp[j] a[i]; // 记录使权值和最大的后续节点j d[i] j; } } // 如果当前节点i的最大权值和大于之前记录的最大权值和 if (dp[i] dp[maxi]) // 更新最大权值和对应的节点编号为i maxi i; } // 从最大权值和对应的节点maxi开始按照记录的路径输出路径上的节点 int t maxi; while (t 0) { printf(%d , t); t d[t]; } printf(\n); // 输出从最大权值和对应的节点出发能得到的最大权值和 printf(%d, dp[maxi]); return 0;
} #include stdio.h // 定义一个函数max用于返回两个整数中的较大值
int max(int a, int b) { return a b? a : b;
} int main() { // t表示背包的容量m表示物品的数量 // w数组用于存储每个物品的重量v数组用于存储每个物品的价值 // dp数组是动态规划的核心数组dp[i][j]表示考虑前i个物品背包容量为j时能获得的最大价值 int t, m, w[103], v[103], dp[103][1003]; // 读取背包的容量t和物品的数量m scanf(%d %d, t, m); // 依次读取每个物品的重量和价值并存储到w数组和v数组中 for (int i 1; i m; i) { scanf(%d %d, w[i], v[i]); } // 动态规划核心部分通过两层循环填充dp数组 // 外层循环遍历每个物品从第1个物品到第m个物品 for (int i 1; i m; i) { // 内层循环从背包容量t开始递减到0用于计算在不同背包容量下的最大价值 for (int j t; j 0; j--) { // 如果当前背包容量j大于等于当前物品i的重量w[i]说明可以放入该物品 if (j w[i]) { // 此时有两种选择放入物品i价值为dp[i - 1][j - w[i]] v[i]不放入物品i价值为dp[i - 1][j] // 取两者中的较大值作为dp[i][j]的值 dp[i][j] max(dp[i - 1][j - w[i]] v[i], dp[i - 1][j]); } else { // 如果当前背包容量j小于当前物品i的重量w[i]则无法放入该物品 // 此时dp[i][j]的值等于不考虑当前物品i时背包容量为j的最大价值即dp[i - 1][j] dp[i][j] dp[i - 1][j]; } } } // 输出考虑所有m个物品背包容量为t时能获得的最大价值 printf(%d, dp[m][t]); return 0;
}
