华为OJ称砝码

分手后的思念是犯贱 2022-10-01 00:48 215阅读 0赞

问题描述：

现有一组砝码，重量互不相等，分别为m1、m2……mn；他们可取的最大数量分别为x1、x2……xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量。   注：
     称重重量包括0 要对输入数据进行校验   方法原型：public static int fama(int n, int[] weight, int[] nums)

输入：

nt n：n表示有多少组重量不同的砝码，1<=n<=10<><=n<=10<><=n<=10<><=n<=10<><=n<=10<><=n<=10<><=n<=10<><=n<=10<>

int\[\] weight：表示n组砝码的重量，1<=mi<=10<><=mi<=10<><=mi<=10<><=mi<=10<><=mi<=10<><=mi<=10<><=mi<=10<><=mi<=10<>

int\[\] num：表示n组砝码的最大数量，1<=xi<=10<><=xi<=10<><=xi<=10<><=xi<=10<><=xi<=10<><=xi<=10<><=xi<=10<><=xi<=10<>

输出：

利用给定的砝码可以称出的不同的重量数

样例输入：

2 1 2 2 1

样例输出：

**动态规划方法求解**

**　　**设dp\[1000\]数组为标记数组。当dp\[i\]=0时，表示质量为i的情况，目前没有称出；当dp\[i\]=1时，表示质量为i的情况已经称出。

本题目中有多个砝码，我们顺序处理每一个砝码。

当处理第j个砝码，质量为wj时，有下列推导公式：

![17210320-20ffb60530ce43078d9ccc2294546de8.png][]

完整程序代码如下：

#include <iostream>
    
    using namespace std;
    
    
    static int fama(int n, int weight[], int nums[])
    {
    	int dp[1001] = { 0 };
    	dp[0] = 1;
    
    	int sum = 0;
    	for (int i = 1; i <= n; i++)
    	{
    		sum += weight[i] * nums[i];
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= nums[i]; j++)
    		{
    			for (int k = sum; k >= weight[i];k--)
    			{
    				if (dp[k - weight[i]] == 1)
    					dp[k] = 1;
    			}
    		}
    	}
    
    	int count = 0;
    	for (int i = 1; i <= sum; i++)
    	{
    		if (dp[i] == 1)
    			count++;
    	}
    	return count+1;
    }
    
    int main(void)
    {
    	int n;
    	cin >> n;
    	int *weight = new int[n + 1];
    	int *nums = new int[n + 1];
    
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> weight[i];
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> nums[i];
    	}
    
    	cout << fama(n, weight, nums);
    
    	delete[]weight;
    	delete[]nums;
    
    	return 0;
    }

[17210320-20ffb60530ce43078d9ccc2294546de8.png]: /images/20220705/6115cc27632d4c859e32d383594799e5.png