用c++写一个背包问题的代码
时间: 2024-06-01 12:12:58 浏览: 10
以下是一个简单的 C 语言背包问题的代码示例:
#include <stdio.h>
#define MAX_WEIGHT 100 // 背包最大承重
#define MAX_ITEMS 10 // 物品数量
int weights[MAX_ITEMS] = {30, 10, 20, 50, 40, 70, 30, 20, 60, 10}; // 物品重量
int values[MAX_ITEMS] = {50, 60, 140, 60, 80, 100, 90, 120, 70, 30}; // 物品价值
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int n, int w) {
if (n == 0 || w == 0) {
return 0;
}
if (weights[n-1] > w) {
return knapsack(n-1, w);
}
else {
return max(knapsack(n-1, w), values[n-1] + knapsack(n-1, w-weights[n-1]));
}
}
int main() {
int max_value = knapsack(MAX_ITEMS, MAX_WEIGHT);
printf("背包问题的最大价值为:%d\n", max_value);
return 0;
}
该代码使用递归方式解决了背包问题,其中 weights 数组存储了物品的重量,values 数组存储了物品的价值,MAX_WEIGHT 定义了背包的最大承重,MAX_ITEMS 定义了物品的数量。knapsack 函数使用递归方式计算了背包问题的最大价值,max 函数用于比较两个数的大小。在 main 函数中,调用 knapsack 函数计算背包问题的最大价值,并输出结果。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)