上川 发表于 2019-12-18 14:46:03

求大神 帮忙解决下啊 用来教女朋友的

求助 求助！！

bin554385863 发表于 2019-12-18 15:01:26

来，和我一起把颈椎掰直咯

Croper 发表于 2019-12-18 15:53:02

就当背包问题算呗

常十六 发表于 2019-12-18 16:36:24

我不确定你是不是要判断 集装箱的总重量 和 船的总载重的对比。
c1 = int(input('输入船C1的载重量'))
c2 = int(input('输入船C2的载重量'))

weight = []
num = 0
while 1:
    num += 1
    weight_n = int(input('输入集装箱W%d重量'%num))
    weigth.append(weight_n)

    question = input('是否还需要输入：Y/N')
    if question == 'Y' or question == 'y':
      continue
    else:
      break

sum_weight = 0
for i in weight:
    sum_weight += i

if sum_weight <= c1 + c2:
    print('可以装下')
else:
    print('超重了')

yangchenkang 发表于 2019-12-18 17:06:56

题目说的是否有可能，那就设定C1和C2能承受的重量一样，所有集装箱重量一样，集装箱数量为偶数，不就完事了吗

上川 发表于 2019-12-21 15:34:48

常十六 发表于 2019-12-18 16:36
我不确定你是不是要判断 集装箱的总重量 和 船的总载重的对比。
c1 = int(input('输入船C1的载重量'))
c2 ...

谢谢了哈

Croper 发表于 2019-12-21 20:04:19

话说最佳答案有错吧，
比如两艘船载重为6，6
集装箱为3 4 4，那么你不把一个集装箱拆开是装不下的

倒戈卸甲 发表于 2019-12-21 21:59:28

楼上说的很对

hrp 发表于 2019-12-22 00:50:29

最佳答案不是用python写的么，楼主在c\c++区要python答案？

上川 发表于 2019-12-22 22:22:06

hrp 发表于 2019-12-22 00:50
最佳答案不是用python写的么，楼主在c\c++区要python答案？

我只是思路不知道
python 我也学了点最起码能读懂。。

参天小草 发表于 2019-12-23 09:44:16

很明显，最佳答案是错的。题目已经告知，集装箱总重量小于两艘船的总承重。
题目的要求是，判断两艘船各自放m和n-m个集装箱（m为小于n的任意正整数，n为题目给的n），是否有可能两艘船都不超重。
如7楼所说，3+4+4 < 6+6，但是不管你怎样安排，总有一艘船超重。

参天小草 发表于 2019-12-23 10:46:21

from itertools import combinations

C1 = int(input('船1载重C1为：'))
C2 = int(input('船2载重C2为：'))
n = int(input('集装箱总数n为：'))

i = 0
weight_list = []
while i < n:
    i += 1
    weight_list.append(int(input('第%d个集装箱重量为：' % i)))
totle_weight = sum(weight_list)

# 成功的情况将被记录在situations中
situations = []
# 开始排列计算
i = 0
for_C1 = []
while i < n:
    i += 1
    # 将集装箱排列进船1
    for_C1.extend(list(combinations(weight_list, i)))

# 判断是否满足条件
for situation in for_C1:
    C1_weight = sum(situation)
    C2_weight = totle_weight - C1_weight
    if C1_weight < C1 and C2_weight < C2:
      situations.append(situation)

if situations:
    print('共%d种方法实现:' % len(situations))
    print('船1中放置集装箱的重量的各种可能为：', situations)
else:
    print('不可实现')

Croper 发表于 2019-12-23 11:36:28

参天小草 发表于 2019-12-23 10:46


你这样硬算时间复杂度是O,n大一点会算不过来的。

其实只要考虑一艘船，尽量多装。看剩下的另一艘船是否能装下就行。

正如我前面所说，那么这就化简成对其中一艘船求0-1背包问题了

def maxCargoLoad(C,W):
    '''
    贪心算法，在船载重为C，试图装N个货物时，其最大载重为f(N,C),
    有：f(N)=max(W)，f(N-1,C))
    '''

    ret={};
    def loopfunc(C,i):
      if (i<0):
            return 0
      if (not (C,i) in ret):
            choice=
            if (C>=W):
                choice.append(W+loopfunc(C-W,i-1))
            ret[(C,i)]=max(choice)
      return ret[(C,i)]
    return loopfunc(C,len(W)-1)

def CanCarry(C1,C2,W):
    return sum(W)-maxCargoLoad(min(C1,C2),W)<=max(C1,C2)

C1 = int(input('船1载重为：'))
C2 = int(input('船2载重为：'))
W = []
print("输入集装箱重量，以-1结束")
while True:
    w0=int(input())
    if (w0<0):
      break
    W.append(w0)

print("在船的载重为%d %d，集装箱分别重" % (C1,C2),W,"的情况下")
print("可以装下" if CanCarry(C1,C2,W) else "不可以装下")
            

恼火的壳壳 发表于 2019-12-23 23:15:08

# 有两艘船,载重量分别是C1,C2
# 需要运载n个集装箱,集装箱的重量分别是
# Wi(i=0,....,n-1) 且所有集装箱的重量不超过C1+C2
# 却编程确定是否有可能将所有集装箱全部装入两艘船


def isLoadable(C1: int, C2: int, listWi: list):
    listWi.sort(reverse=True)
    for i in listWi:
      if C1 >= 0 and C2 >= 0:
            if C2>C1:
                C1,C2=C2,C1
            C1 = C1 -i
      if C1 <0 or C2<0:
            return '承载失败'
    return '承载成功'


if __name__ == '__main__':
    C1, C2, listWi = None, None, None

    try:
      C1 = int(input('请输入第一艘船的载重(整数):'))
      C2 = int(input('请输入第二艘船的载重(整数):'))
      listWi = list(eval(input('请输入集装箱的重量(如:10,23,10):')))
    except TypeError:
      print('输入的格式有误,请重新输入')
    print(C1,C2,listWi)
    if C1 and C2 and listWi:
      print(isLoadable(C1, C2, listWi))

参天小草 发表于 2019-12-24 10:34:56

Croper 发表于 2019-12-23 11:36
你这样硬算时间复杂度是O,n大一点会算不过来的。

其实只要考虑一艘船，尽量多装。看剩下的另一艘 ...

算法大佬{:5_92:}

Croper 发表于 2019-12-24 13:44:48

恼火的壳壳 发表于 2019-12-23 23:15
# 有两艘船,载重量分别是C1,C2
# 需要运载n个集装箱,集装箱的重量分别是
# Wi(i=0,....,n-1) 且所有集装 ...

试试15 15，
集装箱是,这样是可以其实装下的 。。^_^
页: [1]
查看完整版本: 求大神 帮忙解决下啊 用来教女朋友的