回溯算法，非算法高手勿进！
给定物品n件，他们的重量分别是w[0]，w[1]，……w[n-1]，物品的价值分别为v[0]，v[1]，……v[n-1]，另有一个背包，它可以容纳的总重量为w。设计一种物品挑选方案，要求从这n件物品中所选取的物品的总重量不超过背包的容量w，使选中物品的价值之和最大。
这个是很常见的背包回溯算法，谁能用php写一下！
这个是很常见的背包回溯算法，谁能用php写一下！
作者: baoxiaohua 发布时间: 2011-06-08
这个题至少要一个小时， 我说思路， 让别人做吧。
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
3. 对r数组里的每个子集里的项转换成相对应的v值， 并分别求和（赋值数组wv),
4. 对wv数组排序， 得出对大的值的键就是结果。
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
3. 对r数组里的每个子集里的项转换成相对应的v值， 并分别求和（赋值数组wv),
4. 对wv数组排序， 得出对大的值的键就是结果。
作者: coolesting 发布时间: 2011-06-08
2 ...... 选出所有子集里的项的和小于w重量的子集
-----------------------------
就是对子集项求和， 如
{1,3,5} --> (1+3+5) < w
{2,6} --> (2+6) < w
-----------------------------
就是对子集项求和， 如
{1,3,5} --> (1+3+5) < w
{2,6} --> (2+6) < w
作者: coolesting 发布时间: 2011-06-08
另外， 这个和回溯算法有点不同， 回溯算法计算出来的子集是有顺序的，
这里的需求计算出来的子集是没顺序的 ， 更像是计算笛卡尔乘积多点。
这里的需求计算出来的子集是没顺序的 ， 更像是计算笛卡尔乘积多点。
作者: coolesting 发布时间: 2011-06-08
coolesting思路不错
其实这道题的思路网络上早就有了，
有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的
所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个
别到时候百度时候找不到PHP写的回溯案例
其实这道题的思路网络上早就有了，
有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的
所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个
别到时候百度时候找不到PHP写的回溯案例
作者: baoxiaohua 发布时间: 2011-06-08
引用 4 楼 baoxiaohua 的回复:
coolesting思路不错
其实这道题的思路网络上早就有了，
有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的
所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个
别到时候百度时候找不到PHP写的回溯案例
coolesting思路不错
其实这道题的思路网络上早就有了，
有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的
所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个
别到时候百度时候找不到PHP写的回溯案例
好,这个伟大的任务就交给你了......
作者: helloyou0 发布时间: 2011-06-08