算法-运石头过河最少次数问题

Question

有大大小小的一堆石头要用船拉到河对岸
--石头有m块，每块的重量已知
--船每次只能装k块石头，并且装载重量不可以超过w
--想求出最少几趟能把全部石头运过河。

---

例1
石头有9块，重量分别是1,2,3,4,5,6,7,8,9
k=3
w=15
结果是，最少3次就可以运完。

---

例2
石头有9块，重量分别是10,20,30,40,50,61,70,80,90
k=3
w=152
结果是，最少3次就可以运完。

---

例3
石头有9块，重量分别是2,7,9,9,11,16
k=3
w=18
结果是，最少3次就可以运完。

---

例4
石头有9块，重量分别是1,1,1,5,6,6,7,9,9
k=3
w=15
那么结果是，最少 4 次才可以运完。

---

考虑过了背包算法，但是发现背包算法并不能很好解决这个问题。
也有人说可以用 多背包算法，但是一直没有弄明白什么是多背包问算法。

请大家帮帮忙给看一下有没有什么好的思路

Answer 1

每次从大到小，选出最合适的解集合

 import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Denio
{

/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
System.out.println("每次块数：n");
int k = sc.nextInt();
System.out.println("每次重量上限：n");
int w = sc.nextInt();
List<Integer> list = new ArrayList<Integer>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.add(61);
list.add(70);
list.add(80);
list.add(90);
int i = 1;
while (list.size() > 0)
{
int number = 0;// 已有的数量
int weight = 0;// 剩下的重量
int index = list.size() - 1;
System.out.println("第" + i + "次选择:");
weight = w;
while (number < k && index >= 0)
{
weight = weight - list.get(index);
if (weight < 0)
{
weight += list.get(index);
index--;
continue;
}
else
{
System.out.println(list.get(index));
list.remove(index);
number++;
index--;
}
}
System.out.println("t第" + i + "次选择结束n");
i++;
}
}

}

，将其余情况排除。直到集合为空为止。

Answer 2

个人觉得最少次数，另外一层的意思就是每次运送的时候在不超过运算总量和总重量的情况下尽可能的接近总量和总重量的分组

所以我的想法就从大到小排序后，依次将最大值填包，填包的依据就是不超过当前包的总量和总重量

石头有9块，重量分别是1,2,3,4,5,6,7,8,9
k=3
w=15

排序后 9, 8, 7, 6, 5, 4, 3, 2, 1

申请p1，p1k = 3， p1w = 15， 是否有满足tk = p1k = 3, tw <= p1w = 15,

当前9, 剩下的结果中是否满足 t1k = p1k - 1 = 2, t1w <= p1w - 9 = 6
当前8，8 > t1w pass
当前7, 7 > t1w pass
当前6, 6 = t1w, 1 < t1k 剩下的结果 5, 4, 3, 2, 1，是否有满足 t2k = 2, t2w <= t1w
// ps：假设没有满足,则p1填入的是9，6
当前5，5 < t2w, 剩下的结果 4, 3, 2, 1, 是否满足 t3k = 1, t3w <= t2w - 5 = 1
当前4, 4 > t3w pass
当前3, 3 > t3w pass
当前2, 2 > t3w pass
当前1, 1 = t3w , 1 = t3k

p1, 装填 9, 5, 1
结果剩下

8, 7, 6, 4, 3, 2

申请p2，p2k = 3， p2w = 15， 是否有满足tk = p2k = 3, tw <= p2w = 15,
当前8, 剩下的结果中是否满足 t1k = p2k - 1 = 2, t1w <= p2w - 8 = 7
当前7, 7 = t1w, 1 < t1k 剩下的结果 6, 4, 3, 2，是否有满足 t2k = 2, t2w <= t1w
当前6，6 < t2w, 剩下的结果 4, 3, 2, 是否满足 t3k = 1, t3w <= t2w - 6 = 1
当前4, 4 > t3w pass
当前3, 3 > t3w pass
当前2, 2 > t3w pass
pass
当前4, 3 < t2w, 剩下的结果 3, 2, 是否满足 t3k = 1, t3w <= t2w - 4 = 3
当前3, 3 = t3w , 1 = t3k

p2, 装填 8, 4, 3
结果剩下

7, 6, 2

申请p3，p3k = 3， p3w = 15， 是否有满足tk = p3k = 3, tw <= p3w = 15
当前7, 剩下的结果中是否满足 t1k = p3k - 1 = 2, t1w <= p3w - 7 = 8
当前6，6 < t1w, 剩下的结果 2, 是否满足 t2k = 1, t2w <= t1w - 6 = 2
当前2, 2 = t2w, 1 = t2k

p3, 装填 7, 6, 2

10,20,30,40,50,61,70,80,90

石头有9块，重量分别是1,2,3,4,5,6,7,8,9
k=3
w=152

排序后 90, 80, 70, 60, 50, 40, 30, 20, 10

申请p1，p1k = 3， p1w = 152， 是否有满足tk = p1k = 3, tw <= p1w = 152,

当前90, 剩下的结果中是否满足 t1k = p1k - 1 = 2, t1w <= p1w - 90 = 62
当前80，80 > t1w pass
当前70, 70 > t1w pass
当前60, 60 < t1w, 剩下的结果 50, 40, 30, 20, 10，是否有满足 t2k = 1, t2w <= t1w - 60 = 2
当前50, 50 > t2w pass
当前40, 40 > t2w pass
当前30, 30 > t2w pass
当前20, 20 > t2w pass
当前10, 10 > t2w pass
当前60, 60 < t1w, 1 < t1k1 剩下的结果 50, 40, 30, 20, 10，是否有满足 t2k = 2, t2w <= t1w
当前50，50 < t2w, 剩下的结果 40, 30, 20, 10, 是否满足 t3k = 1, t3w <= t2w - 50 = 12
当前40, 40 > t3w pass
当前30, 30 > t3w pass
当前20, 20 > t3w pass
当前10, 10 < t3w, 1 = t3k

p1, 装填 90, 50, 10
结果剩下

80, 70, 60, 40, 30, 20

申请p2，p2k = 3， p2w = 152， 是否有满足tk = p2k = 3, tw <= p2w = 152,
当前80, 剩下的结果中是否满足 t1k = p2k - 1 = 2, t1w <= p2w - 80 = 72
当前70, 70 < t1w, 剩下的结果 60, 40, 30, 20，是否有满足 t2k = 1, t2w <= t1w - 70 = 2
当前60, 60 > t2w pass
当前40, 40 > t2w pass
当前30, 30 > t2w pass
当前20, 20 > t2w pass
当前70, 70 < t1w, 1 < t1k 剩下的结果 60, 40, 30, 20，是否有满足 t2k = 2, t2w <= t1w
当前60，60 < t2w, 剩下的结果 40, 30, 20, 是否满足 t3k = 1, t3w <= t2w - 60 = 12
当前40, 40 > t3w pass
当前30, 30 > t3w pass
当前20, 20 > t3w pass
当前60，60 < t2w, 1 < t2k 剩下的结果 40, 30, 20, 是否满足 t3k = 2, t3w <= t2w
当前40, 40 < t3w, 剩下的结果 30, 20, 是否满足 t3k = 1, t3w <= t2w - 40 = 32
当前30, 30 < t3w , 1 = t3k

p2, 装填 80, 40, 30
结果剩下

70, 60, 20

申请p3，p3k = 3， p3w = 152， 是否有满足tk = p3k = 3, tw <= p3w = 152
当前70, 剩下的结果中是否满足 t1k = p3k - 1 = 2, t1w <= p3w - 70 = 82
当前60，60 < t1w, 剩下的结果 20, 是否满足 t2k = 1, t2w <= t1w - 60 = 22
当前20, 20 < t2w, 1 = t2k

p3, 装填 70, 60, 20

Answer 3

这个问题应该是搜索加剪支
n块石头。最多n次送完。每块重量都小于约束
确定第一次送几块 送哪几块 可能有
树中每个节点状态是 当前第几批运送石头 剩余的石头编号 当前批次的石头
当当前批次不能加石头时 增加运送批次 开辟新的分支
每个父亲节点 的总的运送批次是所有子节点中最小的
因此如果当前节点批次超过或等于当前最小的批次数 则可以减去分支

因此根结点。剩余所有石头 批次1 批次总重量0
分支 1 第一个剩余石头 放入批次。
分支2 第一个剩余石头不放入批次1。 标记剩余石头第一个不能放入批次1

在分支1中。 剩余除1外的石头 判断超重 没有则继续放入 有则批次加1开新的分支
分支2中 在所有可能放入的石头中 尝试。如果当前批次已满 则将所有保留石头加入剩余中建立新的分支

因此每个分支有保留石头。可用石头 当前批次 批次总重
每次做新的分支这些数据结构都要复制一份新的
每次新分支 检查是否可以减去分支

思路有点类似minmax 树。空间 时间消耗都不小