装修设计网站哪家好,wordpress 避免被刷死,青少年活动中心网站建设依据,接网站建设单子的网站【问题描述】 设有
1g
、
2g
、
3g
、
5g
、
10g
、
20g
的砝码各若干枚#xff08;其总重
1000
#xff09;#xff0c;用他们能称出的重量的种类数。 【输入文件】
a1 a2 a3 a4 a5 a6
#xff08;表示
1g
砝码有
a1
个#xff0c;
2g
砝码有
a2
个…【问题描述】 设有
1g
、
2g
、
3g
、
5g
、
10g
、
20g
的砝码各若干枚其总重
1000
用他们能称出的重量的种类数。 【输入文件】
a1 a2 a3 a4 a5 a6
表示
1g
砝码有
a1
个
2g
砝码有
a2
个…
20g
砝码有
a6
个中间有空格。 【输出文件】
TotalN N
表示用这些砝码能称出的不同重量的个数但不包括一个砝码也不用的情况。 【输入样例】
1 1 0 0 0 0
【输出样例】
TOTAL3 思路
很简单的背包问题的变形。
构建子结构opt[i][j]表示从前i个砝码中选取有限个若能组合成j则值为1否则值为0。
那么opt[i][j] 取或{opt[i-1][j-w[i]*k]} 其中j - w[i]*k 0 并且0 k a[i]
