国外网站空间租用费用站长工具收录
背包问题的解决过程
在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(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)；
由此可以得出递推关系式：
j<w(i) V(i,j)=V(i-1,j)
j>=w(i) V(i,j)=max｛V(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;
}