算法背包问题代码和伪代码c语言

一、01背包问题

伪代码：

1.初始化dp数组，dp[i][0] = 0，dp[0][j] = 0
2.对于每个物品i，从j = 1到j = V，逆序枚举背包容量：
3.如果j < w[i]，说明这个物品放不下，则dp[i][j] = dp[i-1][j]
4.否则，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
5.最终结果存储在dp[N][V]中

C++代码：

int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量

int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
if (j < w[i]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}

二、完全背包问题

伪代码：

1.初始化dp数组，dp[i][0] = 0，dp[0][j] = 0
2.对于每个物品i，从j = 1到j = V，正序枚举背包容量：
3.对于每个物品i，从j = w[i]到j = V，正序枚举背包容量：
4.dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])
5.最终结果存储在dp[N][V]中

C++代码：

int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量

int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; 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]);
}
}
}
return dp[N][V]; // 返回最终结果
}

三、多重背包问题

伪代码：

1.初始化dp数组，dp[i][0] = 0，dp[0][j] = 0
2.对于每个物品i，从j = 1到j = V，正序枚举背包容量：
3.对于每个物品i，从j = w[i]到j = V，正序枚举背包容量：
4.对于每个物品i，从k = 0到k = min(v[i], j/w[i])，正序枚举物品数量：
5.dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i])
6.最终结果存储在dp[N][V]中

C++代码：

int dp[MAX_N][MAX_V]; // dp数组
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int N, V; // 物品数量和背包容量

int solve() {
memset(dp, 0, sizeof(dp)); // 初始化dp数组

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 0; k <= min(v[i], j/w[i]); k++) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i]);
}
}
}
return dp[N][V]; // 返回最终结果
}