Sum It Up POJ 1564 HDU 杭电1258【DFS】_problem description given a specified total t and -程序员宅基地

Problem Description

Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four different sums that equal 4: 4,3+1,2+2, and 2+1+1.(A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

Input

The input will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1,...,xn. If n=0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12(inclusive), and x1,...,xn will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.

Output

For each test case, first output a line containing 'Sums of', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line 'NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distince; the same sum connot appear twice.

Sample Input

  
  
   
    
   
   4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0

Sample Output

  
  
   
    
   
   Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25

#include<stdio.h>
#include<string.h>
int sum,n;
int a[1010];
int res[1010]={10000};
bool vis[1010];
int j;
bool flag=0;
void DFS(int m,int cnt)
{
	int i;//这个i DFS时要用上，且作用很大，一定得放在里面，我一开始定义了个全局变量，找了快两小时 才找到 
	if(m==0)
	{
		flag=1;
		for(j=1;j<cnt-1;++j)
			printf("%d+",res[j]);
		printf("%d\n",res[j]);
		return ;
	}
	for(i=1;i<=n;++i)
	{
		//
		if(!vis[i]&&m-a[i]>=0&&a[i]<=res[cnt-1])
		{
			vis[i]=1;
			res[cnt]=a[i];                                             
			DFS(m-a[i],cnt+1);
			vis[i]=0;
			while(a[i]==a[i+1]&&i<=n) ++i;
		}
	}

}
int main()
{
	int i;
	while(~scanf("%d%d",&sum,&n),sum+n)
	{
		flag=0;
		for(i=1;i<=n;++i)
		{
			scanf("%d",a+i);
		}
		printf("Sums of %d:\n",sum); 
		memset(vis,0,sizeof(vis));
		DFS(sum,1);
		if(!flag)printf("NONE\n");
	}
	return 0;
}

本文链接：https://blog.csdn.net/yuzhiwei1995/article/details/47607909

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

slam特征点深度 svd_视觉SLAM（五）特征点提取与匹配-程序员宅基地

文章浏览阅读445次。特征点法视觉里程计特征点提取与匹配经典 SLAM 模型中以位姿路标( Landmark )来描述 SLAM 过程? 路标是三维空间中固定不变的点，能够在特定位姿下观测到? 数量充足，以实现良好的定位? 较好的区分性，以实现数据关联在视觉 SLAM 中，可利用图像特征点作为 SLAM 中的路标特征点是图像中具有代表性的部分；具有可重复性，可区别性，高效，本地的特点特征点的信息? 位置、大小、方向、..._slam有深度的特征值

Grafana 设置 Right Y_grafana right y-程序员宅基地

文章浏览阅读2.8k次。Grafana 设置 Right Y1，Grafana 设置 Right Y1，Grafana 设置 Right Y参考：第二个Y轴设置_grafana right y

当面试被问到jvm（Java虚拟机）时，如何将面试官引入自己的节奏？-程序员宅基地

文章浏览阅读1.1w次，点赞74次，收藏69次。作为一名Java开发工程师，不管是校招还是社招jvm一定是必问必会的知识点。虽然说真正开发中用到的不多，甚至可以说用不到（对于刚入行或者Java初级），但是当面试官问出来，就是想考察你对知识的一个广度，如果你能答得很好，那么恭喜你，你已经赢得面试官的好感。在接下来的面试中你会很自信。当然如果你对jvm了解的很深刻，你还可以将面试官引导到自己的节奏。在做自我介绍的时候可以可以强调自己熟悉jvm，那么面试官就有很大概率问到jvm。这篇文章就来详细的介绍一下面试中遇到有关jvm相关面试题该怎么回答。

Collaborative Fairness in Federated Learning论文阅读笔记-程序员宅基地

文章浏览阅读771次。论文地址：https://arxiv.org/abs/2008.121611.介绍大多数现有的分布式或FL框架忽略了参与的一个重要方面：协作公平性。特别是，所有参与者都可以收到相同或类似的模型，而不管他们的贡献如何。为了解决这个问题，本文研究了FL中的协作公平性，并提出了一个新的协作公平联合学习（CFFL）框架，该框架利用声誉强制参与者收敛到不同的模型，从而在不影响预测性能的情况下实现公平性。在基准数据集上的大量实验表明，CFFL实现了高公平性，提供了与分布式框架相当的精度，并且优于标准框架。_collaborative fairness in federated learning

李航：深度学习还局限在复杂的模式识别上_李航机器学习的不足-程序员宅基地

文章浏览阅读4.7k次，点赞2次，收藏2次。转载自：http://www.csdn.net/article/2015-07-03/2825125华为技术有限公司诺亚方舟实验室主任李航认为，机器学习、数据挖掘和人工智能的研究，对华为未来的智能通信网络、智能企业管理、智能信息助手三个应用方向很有帮助，比如机器学习对SDN的控制能力、网络优化、人机交互、跨国交流等，都可以发挥很大的作用。诺亚方舟实验室已经将采用深度学习（DL）提升_李航机器学习的不足

【论文阅读】Bag of Tricks for Image Classification with Convolutional Neural Networks-程序员宅基地

文章浏览阅读1.5k次。Bag of Tricks for Image Classification with Convolutional Neural Networks本文作者总结了模型训练过程中可以提高准确率的方法,如题，作者说 bag of tricks，阅读了一遍文章，有用的内容挺多，为了比赛上分，可以一试，总结如下。文中提到的方法在GLuonCV 0.3中有实现，可以参考这个源代码。文中提到技巧不仅可以应用..._bag of tricks for image classification

随便推点

随笔--解包打包的妙用，Python与配置文件的联用_gambit和python-程序员宅基地

文章浏览阅读251次。1. 解包打包妙用元组a=(1,2,3)print(*a) # 解包def fun(*args,c): print(args) # (1,2)fun(1,2,c=3)字典def fun1(**a): print(a)def fun2(**a): print(a) print(*a) # 一个*解除的是键 'a' 'b' 'c' ..._gambit和python

solidworks怎么新建坐标系为最高坐标系_solidworks2022 坐标系-程序员宅基地

文章浏览阅读518次。首先先在想要建立坐标系的地方画垂直两条线，特征里面-参考几何体-坐标系，选择刚画的线设置XY轴，然后另存为STP格式，在另存的选项中，选择刚刚建立的坐标系名称，然后确定，再打开STP图时就是想要的。_solidworks2022 坐标系

LWN：PipeWire，新一代的Linux audio/video bus_pipewire和pulseaudio区别-程序员宅基地

文章浏览阅读4.3k次，点赞2次，收藏10次。关注了就能看到更多这么棒的文章哦～PipeWire: The Linux audio/video busMarch 2, 2021This article was contributed ..._pipewire和pulseaudio区别

图解git使用_forward-port local commits to the updated upstream-程序员宅基地

文章浏览阅读1.7k次。1.基本用法上面的四条命令在工作目录、暂存目录(也叫做索引)和仓库之间复制文件。git add files 把当前文件放入暂存区域。git commit 给暂存区域生成快照并提交。git reset -- files 用来撤销最后一次git add files，你也可以用git reset 撤销所有暂存区域文件。git checkout -- files 把文件从暂存区域复制到_forward-port local commits to the updated upstream head

多选择大内存，总有一个适合的迅为RK3568瑞芯微开发板国产翼辉SylixOS实时操作系统_3568运行ubuntu流畅吗-程序员宅基地

文章浏览阅读422次。核心板：提供连接器与邮票孔两种，商业级2G、商业级4G、商业级8G工业级2G、工业级4G、国产化工业级2G多种核心板引脚兼容，适用于同一底板，产品升级自如，适用于各个应用场合。核心板提供连接器与邮票孔两种，商业级2G、商业级4G、商业级8G工业级2G、工业级4G、国产化工业级2G多种核心板引脚兼容，适用于同一底板，产品升级自如，适用于各个应用场合。集成了双核心架构GPU，ARM G52 2EE、支持OpenGLES1.1/2.0/32OpenCL 2.0、Vulkan 1.1、内嵌高性能2D加速硬件。_3568运行ubuntu流畅吗

数字温度传感器-DS18B20-程序员宅基地

文章浏览阅读2.1k次。64 位光刻 ROM 的排列是：开始 8 位（地址： 28H ）是产品类型标号，接着的 48 位是该 DS18B20 自身的序列号，并且每个 DS18B20 的序列号都不相同，因此它可以看作是该 DS18B20 的地址序列码；在这里要注意的是每个命令字节在写的时候都是低字节先写，例如CCH的二进制为11001100，在写到总线上时要从低位开始写，写的顺序是“零、零、壹、壹、零、零、壹、壹”。DS18B20中的温度传感器完成对温度的测量，用16位二进制形式提供，形式表达，其中S为符号位。_ds18b20