html网站开发实战教程,做推广怎么赚钱,php网站开发介绍,网站建设与网页设计课程设计【问题描述】 设有
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]
