首先看一下题
描述
现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。注：
称重重量包括 0
数据范围：每组输入数据满足 1≤n≤10 ， 1≤mi≤2000 ， 1≤xi≤10
输入描述：
对于每组测试数据：
第一行：n --- 砝码的种数(范围[1,10])
第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000])
第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])输出描述：
利用给定的砝码可以称出的不同的重量数
示例1
输入：
2 1 2 2 1输出：
5说明：
可以表示出0，1，2，3，4五种重量。
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.现在有n种砝码
2.重量互不相等
3.分别为m1,m2,m3...mn;
4.每种砝码对应的数量为x1,x2,x3...xn。
5.现在要用这些砝码去称物体的重量（放在同一侧），
6.问能称出多少种不同的重量。
7.称重重量包括0
8.数据范围：每组输入数据满足n大于等于1小于等于10，mi大于等于1小于等于2000，xi大于等于1，小于等于10
9.输入描述：对于每组测试数据：
第一行：n 法码的种数（范围[1,10]）
第二行：m1 m2 m3 .. mn 每种砝码的重量（范围[1,2000]）
第三行：x1 x2 x3 ... xn 每种砝码对应的数量（范围[1,10]）
10.输出描述：利用给定的砝码可以称出的不同的重量数
二、解题思路
1.首先我们最大可以称量的重量是2000*10*10 = 200000
2.我们可以定义一个int dp[200001] = {0};用来标记我们是否已经称量过某个重量
3.我们定义一个int count = 0；用来计算我们可以称量的不同的重量数
4.我们定义一个int n 用来存储砝码的种数
5.我们定义一个int m[n]用来存放每种砝码的重量
6.我们定义一个int x[n];用来存放每种砝码对应的数量
7.之后我们希望计算不同砝码的组合能够组成的重量值
8.计算出来重量值如果dp[重量] == 0;那么我们count++，dp[重量] = 1;
如果已经计算过了，我们不重复计算
三、具体步骤
使用的语言是C
#include <stdio.h>int main() {int n;while(scanf("%d", &n) != EOF) {int m[n];for(int i = 0; i < n; i++) {scanf("%d", &m[i]);}int x[n];for(int i = 0; i < n; i++) {scanf("%d", &x[i]);}// total用来计算我们可以称量的最大重量int total = 0;for(int i = 0; i < n; i++) {// 使用每种砝码的重量乘以数量得到每种砝码最大承重量，再相加total += m[i] * x[i];}// 定义一个数组可以表示某个重量是否称量过，第一个元素为1（代表称量过）int arr[200001] = {1};for(int i = 0; i < n; i++) {// 循环遍历每种砝码for(int j = 0; j < x[i]; j++) {// 遍历当前砝码(第i个)的个数x[i]for(int k = total; k >= 0; k--) {// 遍历所有的重量if(arr[k]) {// 如果遇到称量过的重量（以0为开始），我们将当前的这个砝码的重量也加上去，标记为称量过了arr[k + m[i]] = 1;}}}}int count = 0;for (int i = 0; i <= total; i++) {if(arr[i] == 1) {count++;}}printf("%d\n", count);return 0;}
}
