Description
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解0-1背包问题。
0-1 背包问题描述如下：给定n 种物品和一个背包。物品i的重量是wi，其价值为vi ，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2 种选择，即装入背包或不装入背包。不能将物品i 装入背包多次，也不能只装入部分的物品i。
Input
输入由多组测试数据组成。
每组测试数据输入的第一行有2个正整数n和c。n是物品数，c是背包的容量。接下来的1 行中有n个正整数，表示物品的价值。第3 行中有n个正整数，表示物品的重量。
Output
对应每组输入，输出的2行是装入背包物品的最大价值和最优装入方案。
Sample Input
5 10
6 3 5 4 6
2 2 6 5 4
Sample Output
15
1 1 0 0 1
2020-01-03 11:17:35
2KB
1
bag greedy-beibao sort2 3个函数，把函数放到matlab的work文件夹下，运行时直接调用bag就可以。然后输入待装包物品总数，各物品的编号，重量，价值。 程序会自动完成，含把物品按单位价值排序的功能，自己写的。保证可以运行无错误。
2019-12-21 21:09:42
933B
1
分支限界法0-1背包问题
示例输入（规定物品数量为10，背包容量为50，输入为20个数，前十个为物品重量，后十个数为物品价值）：
12
3
11
5
6
8
9
4
7
10
6
2
7
3
2
9
8
10
4
5
示例输出（最大价值）：
44
2019-12-21 20:02:56
49KB
1
1) 动态规划法求解问题的一般思路，动态规划法求解本问题的思路及其C/C++程序实现与算法的效率分析。
2) 贪心算法在0-1背包问题求解中的应用
3) 回溯法求解问题的一般思路，回溯法求解本问题的思路及其C/C++程序实现与算法的效率分析。
4) 分支限界法求解问题的一般思路，分支限界法求解本问题的思路及其C/C++程序实现与算法的效率分析。
有代码！！
2019-12-21 19:43:22
58KB
1