UC知道C语言中的砝码称重问题
来源：百度知道 编辑：UC知道 时间：2024/05/17 13:35:59
现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重量不超过1000克，且砝码只能放在天平的一端）
输入方式：a1 a2 a3 a4 a5 a6
(表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个)
输出方式:Total=N
(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)
如:输入:1 1 0 0 0 0
输出:Total=3 表示可以称出1g,2g,3g三种不同的重量。
输入方式：a1 a2 a3 a4 a5 a6
(表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个)
输出方式:Total=N
(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)
如:输入:1 1 0 0 0 0
输出:Total=3 表示可以称出1g,2g,3g三种不同的重量。
1、以f(k):几种砝码组合能称出k的重量为状态DP全部n个砝码，然后枚举去掉的m个砝码的组合，对每种组合再DP一次，从f中减掉，剩下的就是能称出的不同重量，复杂度O(n * C(n, m) * m * max(a))≤38760000。
2、例程：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<memory.h>
/*a数组用于存储从n个整型数
* 据中取k个数字的数组下标值
* */
int a[100]={0};
/*data数组用于存储实际的数据,也就是所有砝码的
* 重量
* */
int data[4]={2,2,3,3};
/*sum数组用于保存再data中取k个树的和,注意
* 没有唯一化处理,也就是说可能里面存在重复
* 唯一化处理使用函数unique;
* */
int sum[100] = {0};
/*index_sum用于记录sum中最后一个数据的索引值
* */
int index_sum = 0;
/*这是一个递归实现,用于获取从[start,length-num]的
* 某一位数,这个位数对应了data数组的下标,num是从
* data中取几位数的,fujia是一个附加参数,用于记录当
* 前获取了