Py小郑 2022-03-29 09:11 采纳率: 98.7%
浏览 134
已结题

有关蓝桥杯砝码称重 DP问题

我已经思考过很久了,就是不知道问题出在哪?

img

n=int(input())

v=list(map(int,input().split()))
v.insert(0,0)
M=sum(v)
#0是称不出来的,称重范围(0,M]
dp=[[0]*(2*M) for i in range(n+1)]#前i个物品能否组合出j的重量
#设置2M为了数组下标防止越界

for i in range(1,n+1):
    for j in range(1,M+1):
        dp[i][j]=dp[i-1][j]
        if v[i]==j:
            dp[i][j]=1
        if dp[i][j]==1:
            continue
        if j>v[i]:
            dp[i][j]=dp[i-1][j-v[i]]
        elif j<v[i]:
            dp[i][j]=max(dp[i-1][v[i]+j],dp[i-1][v[i]-j])
        else:
            pass
ans=0
for i in dp[-1]:
    if i==1:
        ans+=1
print(ans)


我的思路:先在v数组添加一个(0,0)代表第0个砝码的重量是0,方便后面下标书写。
然后dp[i][j]代表前i个物品能否称重出j的重量,可以为1,不可以为0
dp[i][j]至少等于dp[i][j-1],第一步。如果第i个物品已经等于j,dp[i][j]=1,第二步。
经过第一部和第二步,如果dp[i][j]已经为1,那么就不需要在做下去了,进入下一次循环dp[i][j+1]
否则,即dp[i][j]=0,如果j过大,只需要考虑前i-1个物品能否凑出j-v[i]
如果j过小,我们只需要考虑前i-1个物品能否凑出v[i]+j,或v[i]-j,可是程序只对了20%,问题错在哪呢?
下面是正确的代码:

    n=int(input())
    #dp[i][j]表示加上第i个砝码,j的重量是否可以被称出,可以被称出则j=1,不可以则j=0
    a=list(map(int,input().split()))
    sum=0 #sum是j的范围
    for i in a:
        sum+=i
    dp=[[0]*2*sum for i in range(n+1)]      #*列   for in 行
    result=0
    for p in range(1,n+1):
        for q in range(1,sum+1):
            dp[p][q]=dp[p-1][q]
            if dp[p][q] == 0:   #只看前p-1个无法称量的
                if a[p-1]==q:
                    dp[p][q]=1
                if dp[p-1][a[p-1]+q]:  #放在不同侧(即相减)  返过去判断就要相加
                    dp[p][q]=1
                if dp[p-1][abs(a[p-1]-q)]:
                    dp[p][q]=1
    for i in dp[n]:
        if i==1:
            result+=1
    print(result)


请求指导!

  • 写回答

2条回答

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 系统已结题 4月13日
      • 已采纳回答 4月5日
      • 创建了问题 3月29日

      悬赏问题

      • ¥15 在线教育培训平台,主要以点播视频和在线练习测试为主,除将视频做切片外,有其他哪种方式降低流量?(关键词-带宽速率)
      • ¥20 用c语音或c++实现银行叫号系统
      • ¥15 人工智能 规则正向演绎和推理
      • ¥20 基于STM32F401的电子密码锁设计
      • ¥15 famamacbeth回归中遇到only size-1 arrays can be converted to Python scalars,求解答
      • ¥15 单片机多个自锁按键的编程实践
      • ¥15 用python操作redis存储中文后,再取出的数据变成了乱码怎么办?
      • ¥15 C语言简单排序问题有偿求解
      • ¥20 请问图片的代码什么意思
      • ¥15 coq问题求带,有偿