01背包问题分治法,蛮力法,动态规划法c语言
时间: 2023-07-07 22:04:33 浏览: 90
1. 分治法
分治法的思路是将问题划分成更小的子问题,然后分别解决子问题,最后将子问题的解合并起来得到原问题的解。
01背包问题可以采用分治法来解决。具体步骤如下:
1. 将物品按照价值从高到低排序;
2. 将物品分成两组,一组放入背包,一组不放入背包;
3. 对于放入背包的物品,将背包容量减去该物品的重量,再从剩下的物品中选择放入背包的物品;
4. 对于不放入背包的物品,在剩下的物品中选择放入背包的物品;
5. 对于两组物品分别递归上述过程,直到无法再分组为止;
6. 将子问题的解合并起来得到原问题的解。
代码实现:
```c
#include <stdio.h>
#define N 100
int weight[N], value[N];
int max(int a, int b) { return a > b ? a : b; }
int solve(int n, int w) {
if (n == 0 || w == 0) return 0;
if (weight[n] > w) return solve(n - 1, w);
else return max(solve(n - 1, w), solve(n - 1, w - weight[n]) + value[n]);
}
int main() {
int n, w;
printf("请输入物品数量和背包容量:\n");
scanf("%d %d", &n, &w);
printf("请输入每个物品的重量和价值:\n");
for (int i = 1; i <= n; i++) {
scanf("%d %d", &weight[i], &value[i]);
}
printf("背包能够装入的最大价值为:%d\n", solve(n, w));
return 0;
}
```
2. 蛮力法
蛮力法的思路是枚举所有可能的情况,然后找出符合条件的最优解。
01背包问题可以采用蛮力法来解决。具体步骤如下:
1. 枚举所有可能的物品组合,即对于每个物品都有放入背包或不放入背包两种选择;
2. 计算每种组合的总价值,找出其中符合背包容量限制的最大价值;
3. 输出最大价值。
代码实现:
```c
#include <stdio.h>
#define N 100
#define INF 0x3f3f3f3f
int weight[N], value[N];
int max(int a, int b) { return a > b ? a : b; }
int solve(int n, int w) {
int ans = 0;
for (int i = 0; i < (1 << n); i++) { // 枚举所有可能的组合
int sum_w = 0, sum_v = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) { // 选择放入背包的物品
sum_w += weight[j+1];
sum_v += value[j+1];
}
}
if (sum_w <= w) ans = max(ans, sum_v); // 更新最大价值
}
return ans;
}
int main() {
int n, w;
printf("请输入物品数量和背包容量:\n");
scanf("%d %d", &n, &w);
printf("请输入每个物品的重量和价值:\n");
for (int i = 1; i <= n; i++) {
scanf("%d %d", &weight[i], &value[i]);
}
printf("背包能够装入的最大价值为:%d\n", solve(n, w));
return 0;
}
```
3. 动态规划法
动态规划法的思路是将原问题分解成若干个子问题,先求解子问题,再由子问题的解推导出原问题的解。
01背包问题可以采用动态规划法来解决。具体思路如下:
1. 定义状态:设 dp[i][j] 表示前 i 个物品中,容量为 j 的背包能够装入的最大价值;
2. 初始化:dp[0][j] = 0 (0 <= j <= w),dp[i][0] = 0 (1 <= i <= n);
3. 状态转移方程:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) (weight[i] <= j <= w, 1 <= i <= n);
4. 输出结果:dp[n][w]。
代码实现:
```c
#include <stdio.h>
#define N 100
#define INF 0x3f3f3f3f
int weight[N], value[N];
int max(int a, int b) { return a > b ? a : b; }
int solve(int n, int w) {
int dp[N][N];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= w; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = weight[i]; j <= w; j++) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
}
}
return dp[n][w];
}
int main() {
int n, w;
printf("请输入物品数量和背包容量:\n");
scanf("%d %d", &n, &w);
printf("请输入每个物品的重量和价值:\n");
for (int i = 1; i <= n; i++) {
scanf("%d %d", &weight[i], &value[i]);
}
printf("背包能够装入的最大价值为:%d\n", solve(n, w));
return 0;
}
```