2023年8月1日发(作者：)
基础背包问题-⽆界背包问题或完全背包问题-深度优先搜索（递归）基础背包问题 - ⽆界背包问题或完全背包问题 - 深度优先搜索 (递归)1. 基础背包问题有
N 种物品和⼀个承受最⼤重量为
W 的背包。第
i 种物品的重量是
w[i]，价值是
v[i]。求解将哪些物品装⼊背包可使这些物品的重量总和不超过背包容量，且价值总和最⼤。背包问题 (Knapsack problem) 是⼀种组合优化的 NP 完全问题。给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题 (0-1 knapsack problem) 。如果限定物品
j 最多只能选择
maxj 个，则问题称为有界背包问题 (bounded knapsack problem，BKP)。如果不限定每种物品的数量，每种物品都就可以选择任意多个，则问题称为⽆界背包问题或完全背包问题 (unbounded knapsackproblem，UKP)。2. ⽆界背包问题或完全背包问题有
N 种物品和⼀个容量是
V 的背包，每种物品都有⽆限件可⽤。第
i 种物品的体积是
vi，价值是
wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤，输出最⼤价值 10。输⼊格式2 // 测试⽤例个数4 5 // N = 4 物品的类别数，V = 5 背包的容量，最⼤价值 101 2 // v[0] = 1，w[0] = 22 4 // v[1] = 2，w[1] = 43 4 // v[2] = 3，w[2] = 44 5 // v[3] = 4，w[3] = 54 5 // N = 4 物品的类别数，V = 5 背包的容量，最⼤价值 101 22 43 44 52 10 // N = 2 物品的类别数，V = 10 背包的容量，最⼤价值 105 57 84 10 // N = 4 物品的类别数，V = 10 背包的容量，最⼤价值 127 94 53 32 1两个整数
N
V，⽤空格隔开，分别表⽰物品种数和背包容量。接下来有
N ⾏，每⾏两个整数
vi
wi，⽤空格隔开，分别表⽰第
i 种物品的体积和价值。vi 表⽰体积，wi 表⽰价值。0#include using namespace std;int computation = 0;void dfs_v1(int map[100][2], int N, int V, int sumvolume, int sumvalue, int *max_value, int step){ if (sumvolume > V) { return; } if ((sumvalue > *max_value)) { *max_value = sumvalue; } if (step >= N) { computation++; return; } int addvolume = 0, addvalue = 0; // 选这类物品，然后选下⼀类 dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step + 1); // 选这类物品，然后继续选择同类 dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step); dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step); // 不选这类物品，然后选下⼀类 dfs_v1(map, N, V, sumvolume, sumvalue, max_value, step + 1); return;}int inference(int map[100][2], int N, int V){ int ret = 0; int max_value = INT_MIN; int step = 0; int sumvolume = 0; int sumvalue = 0; dfs_v1(map, N, V, sumvolume, sumvalue, &max_value, step); ret = max_value; return ret;}int main(){ clock_t start = 0, end = 0; double cpu_time_used = 0; const char input_txt[] = "D:visual_studio_"; const char output_txt[] = "D:visual_studio_"; freopen(input_txt, "r", stdin); // freopen(output_txt, "w", stdout); start = clock(); printf("Start of the program, start = %ldn", start); printf("Start of the program, start = %ldnn", start); int case_num; cin >> case_num; for (int i = 1; i <= case_num; i++) { int ret = 0; int N = 0, V = 0; int map[100][2] = { 0 }; computation = 0; cin >> N >> V; for (int h = 0; h < N; h++) { cin >> map[h][0] >> map[h][1]; // volume - value } ret = inference(map, N, V); cout << "computation " << i << " = " << computation << endl; cout << "CASE #" << i << " = " << ret << endl; } end = clock(); printf("nEnd of the program, end = %ldn", end); printf("End of the program, end = %ldn", end); cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC; printf("Total time taken by CPU: %fn", cpu_time_used); printf("Exiting of "); fclose(stdin); // fclose(stdout); return 0;}Start of the program, start = 0Start of the program, start = 0computation 1 = 51CASE #1 = 10computation 2 = 51CASE #2 = 10computation 3 = 7CASE #3 = 10computation 4 = 83CASE #4 = 12End of the program, end = 6End of the program, end = 6Total time taken by CPU: 0.006000Exiting of 请按任意键继续. . .
2023年8月1日发(作者：)
基础背包问题-⽆界背包问题或完全背包问题-深度优先搜索（递归）基础背包问题 - ⽆界背包问题或完全背包问题 - 深度优先搜索 (递归)1. 基础背包问题有
N 种物品和⼀个承受最⼤重量为
W 的背包。第
i 种物品的重量是
w[i]，价值是
v[i]。求解将哪些物品装⼊背包可使这些物品的重量总和不超过背包容量，且价值总和最⼤。背包问题 (Knapsack problem) 是⼀种组合优化的 NP 完全问题。给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题 (0-1 knapsack problem) 。如果限定物品
j 最多只能选择
maxj 个，则问题称为有界背包问题 (bounded knapsack problem，BKP)。如果不限定每种物品的数量，每种物品都就可以选择任意多个，则问题称为⽆界背包问题或完全背包问题 (unbounded knapsackproblem，UKP)。2. ⽆界背包问题或完全背包问题有
N 种物品和⼀个容量是
V 的背包，每种物品都有⽆限件可⽤。第
i 种物品的体积是
vi，价值是
wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤，输出最⼤价值 10。输⼊格式2 // 测试⽤例个数4 5 // N = 4 物品的类别数，V = 5 背包的容量，最⼤价值 101 2 // v[0] = 1，w[0] = 22 4 // v[1] = 2，w[1] = 43 4 // v[2] = 3，w[2] = 44 5 // v[3] = 4，w[3] = 54 5 // N = 4 物品的类别数，V = 5 背包的容量，最⼤价值 101 22 43 44 52 10 // N = 2 物品的类别数，V = 10 背包的容量，最⼤价值 105 57 84 10 // N = 4 物品的类别数，V = 10 背包的容量，最⼤价值 127 94 53 32 1两个整数
N
V，⽤空格隔开，分别表⽰物品种数和背包容量。接下来有
N ⾏，每⾏两个整数
vi
wi，⽤空格隔开，分别表⽰第
i 种物品的体积和价值。vi 表⽰体积，wi 表⽰价值。0#include using namespace std;int computation = 0;void dfs_v1(int map[100][2], int N, int V, int sumvolume, int sumvalue, int *max_value, int step){ if (sumvolume > V) { return; } if ((sumvalue > *max_value)) { *max_value = sumvalue; } if (step >= N) { computation++; return; } int addvolume = 0, addvalue = 0; // 选这类物品，然后选下⼀类 dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step + 1); // 选这类物品，然后继续选择同类 dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step); dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step); // 不选这类物品，然后选下⼀类 dfs_v1(map, N, V, sumvolume, sumvalue, max_value, step + 1); return;}int inference(int map[100][2], int N, int V){ int ret = 0; int max_value = INT_MIN; int step = 0; int sumvolume = 0; int sumvalue = 0; dfs_v1(map, N, V, sumvolume, sumvalue, &max_value, step); ret = max_value; return ret;}int main(){ clock_t start = 0, end = 0; double cpu_time_used = 0; const char input_txt[] = "D:visual_studio_"; const char output_txt[] = "D:visual_studio_"; freopen(input_txt, "r", stdin); // freopen(output_txt, "w", stdout); start = clock(); printf("Start of the program, start = %ldn", start); printf("Start of the program, start = %ldnn", start); int case_num; cin >> case_num; for (int i = 1; i <= case_num; i++) { int ret = 0; int N = 0, V = 0; int map[100][2] = { 0 }; computation = 0; cin >> N >> V; for (int h = 0; h < N; h++) { cin >> map[h][0] >> map[h][1]; // volume - value } ret = inference(map, N, V); cout << "computation " << i << " = " << computation << endl; cout << "CASE #" << i << " = " << ret << endl; } end = clock(); printf("nEnd of the program, end = %ldn", end); printf("End of the program, end = %ldn", end); cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC; printf("Total time taken by CPU: %fn", cpu_time_used); printf("Exiting of "); fclose(stdin); // fclose(stdout); return 0;}Start of the program, start = 0Start of the program, start = 0computation 1 = 51CASE #1 = 10computation 2 = 51CASE #2 = 10computation 3 = 7CASE #3 = 10computation 4 = 83CASE #4 = 12End of the program, end = 6End of the program, end = 6Total time taken by CPU: 0.006000Exiting of 请按任意键继续. . .
发布评论