多重部分和问题 dfs

系统管理员 2022-06-16 03:21 174阅读 0赞

## Description ##

有n种不同大小的数字，每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。

## Input ##

首先是一个正整数T(1<=T<=100)

接下来是T组数据

每组数据第一行是一个正整数n(1<=n<=100)，表示有n种不同大小的数字

第二行是n个不同大小的正整数ai(1<=ai<=100000)

第三行是n个正整数mi(1<=mi<=100000)，表示每种数字有mi个

第四行是一个正整数K(1<=K<=100000)

## Output ##

对于每组数据，如果能从这些数字中选出若干使它们的和恰好为K，则输出“Yes”，否则输出“No”，每个输出单独占一行

## Sample Input ##

233 5 83 2 21721 21 14

## Sample Output ##

Yes

No

#include<iostream>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int n,k,a[1010][2],flag,v[1010];
    void dfs(int sum)
    {
    	int i,j;
    	if (flag==1){
    		return ;
    	}
    	if (sum > k){
    		return ;
    	}
    	if (sum == k){
    		flag = 1;
    		return ;
    	}
    	for (i=0; i<n; i++)
    	{
    		if (v[i] < a[i][1])
    		{
    			v[i]++;
    			dfs(sum+a[i][0]);
    			v[i]--;
    		}
    	}
    }
    int main()
    {
    	int T,i,j;
    	cin>>T;
    	while (T--)
    	{
    		cin>>n;
    		for (i=0; i<n; i++){
    			cin>>a[i][0];
    		}
    		for (i=0; i<n; i++){
    			cin>>a[i][1];
    		}
    		cin>>k;
    		flag = 0;
    		memset(v, 0, sizeof(v));
    		dfs(0);
    		if (flag == 1){
    			cout<<"Yes"<<endl;
    		}
    		else{
    			cout<<"No"<<endl;
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 1282 部分和问题(入门题)（dfs）

部分和问题(入门题) 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 0 描述给你n个数(a1,a2,a3.......an) ,是否存在某

不念不忘少年蓝@/ 2024年02月17日 20:21/ 0 赞/ 19 阅读

相关 DFS-部分和

题目描述给定整数序列a1,a2,…,an,判断是否可以从中选出若干数,使它们的和恰好为k. 1≤n≤20 -10^8≤ai≤10^8

怼烎@/ 2023年07月09日 08:25/ 0 赞/ 15 阅读

相关多重背包问题

多重背包问题 1、参考资料 https://blog.csdn.net/qq\_38984851/article/details/81133840 https:/

╰半夏微凉°/ 2022年11月27日 07:24/ 0 赞/ 224 阅读

相关部分和问题

部分和问题时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述给定整数a1、a2、.......an，判断是否可以从中选出若干数，

素颜马尾好姑娘i/ 2022年08月07日 13:50/ 0 赞/ 181 阅读

相关多重部分和问题

问题及代码：有n种不同大小的数字a\[i\]，每种各m\[i\]个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。代码① dp\[i\]表示

傷城~/ 2022年07月24日 11:21/ 0 赞/ 201 阅读

相关 POJ 2392-Space Elevator(多重部分和-多重背包)

Space Elevator <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

雨点打透心脏的1/2处/ 2022年07月24日 11:19/ 0 赞/ 97 阅读

相关 POJ 1276-Cash Machine（多重部分和-dp）

Cash Machine <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

拼搏现实的明天。/ 2022年07月12日 03:59/ 0 赞/ 190 阅读

相关多重部分和问题 dfs

Description 有n种不同大小的数字，每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。 Input 首先是一个正整数T(1<=T<=100

系统管理员/ 2022年06月16日 03:21/ 0 赞/ 175 阅读

相关 dfs解决部分和问题

问题描述：给出n个数，给出和k，能否选出若干个数，使他们的和为k 代码如下 include<stack> include<vector> inclu

布满荆棘的人生/ 2022年05月11日 11:56/ 0 赞/ 218 阅读

相关多重背包问题

转自：[http://www.cnitblog.com/luckydmz/archive/2008/08/06/47719.aspx][http_www.cnitblog.co

青旅半醒/ 2021年12月16日 12:39/ 0 赞/ 318 阅读