本文主要是介绍和为定值的多个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目
输入:数组如:[1,2,4,8,16,32,64], 和一个固定数字100;
输出:选出数组中和为100的几个数的位置。如对于此例子,输出:3, 6, 7。因为4+32+64=100
#coding=utf-8
import sys
def bag(n,m,w,v):res = [[0 for j in range(m+1)]for i in range(n+1)] #n+1 行,m+1列 值为0的矩阵for i in range(1,n+1):for j in range(1,m+1):res[i][j] = res[i-1][j] #0->res[0][1]->res[1][1]if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:#如果res[i-1][j]小于res[i-1][j-w[i-1]]+v[i-1],那么res[i][j]就等于res[i-1][j],否则就等于res[i-1][j-w[i-1]]+v[i-1]res[i][j] = res[i-1][j-w[i-1]]+v[i-1]return res
def show(n,m,w,res):x = [False for i in range(n)]j = mfor i in range(n,0,-1):if res[i][j]!=res[i-1][j]:x[i-1] = Truej-=w[i-1]print(sum(x))for i in range(n):if x[i]:print (i+1)
if __name__ == "__main__":# 读取第一行的nn = int(sys.stdin.readline().strip())values = []for i in range(n):# 读取每一行line = sys.stdin.readline().strip()# 把每一行的数字分隔后转化成int列表values.append(int(line))#n=7m=100#w=[1,2,4,8,16,32,64]#v=[1,2,4,8,16,32,64]res = bag(n,m,values,values)#print (res)show(n,m,values,res)
这篇关于和为定值的多个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!