- http://ac.nbutoj.com/Problem/view.xhtml?id=1479
[1479] How many
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
- There are N numbers, no repeat. All numbers is between 1 and 120, and N is no more than 60. then given a number K(1 <= K <= 100). Your task is to find out some given numbers which sum equals to K, and just tell me how many answers totally,it also means find out hwo many combinations at most.
- 输入
- There are T test cases. For each case: First line there is a number N, means there are N numbers. Second line there is a number K, means sum is K. Third line there lists N numbers. See range details in describe.
- 输出
- Output the number of combinations in total.
- 样例输入
2
5
4
1,2,3,4,5
5
6
1,2,3,4,5- 样例输出
2
3- 01背包||DP代码:
-
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h> using namespace std;
int dp[]; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(dp,,sizeof(dp));
dp[]=;
int i,j;
for(i=;i<n;i++)
{
int a;
scanf("%d",&a);
getchar();
for(j=m;j>=;j--)
{
if(a+j<=m)
{
dp[a+j]+=dp[j];
}
}
// for(j=0;j<=m;j++) printf("%d ",dp[j]); putchar(10);
}
printf("%d\n",dp[m]);
}
return ;
}DFS代码:
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; int n,m;
int a[],mark[];
int cnt; void dfs(int x,int s){
if(s==){
cnt++;
return;
}
int i;
for(i=x;i<n;i++){
if(!mark[i]&&s-a[i]>=){
mark[i]=;
dfs(i+,s-a[i]);
mark[i]=;
}
}
} int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
int i;
for(i=;i<n;i++){
scanf("%d",&a[i]);
getchar();
}
memset(mark,,sizeof(mark));
cnt=;
dfs(,m);
printf("%d\n",cnt);
}
return ;
}
相关文章
- [ChatGPT]-01-chatgpt可以做什么?如何调教
- 蓝桥杯2022李白打酒加强版_dp
- DFS+记忆化剪枝--[NOIP2017 普及组] 棋盘
- vue尚品汇商城项目-day01【1.vue-cli脚手架初始化项目生成文件的介绍】
- python数据分析-matplotlib折线图知识总结01
- 初写--数据结构-->顺序表__01
- 轻量级CI/CD发布部署环境搭建及使用_01_基本介绍
- (原创)【B4A】一步一步入门05:控件、公有属性、水平锚定、垂直锚定(控件篇01)
- UVA 10254 - The Priest Mathematician (dp | 汉诺塔 | 找规律 | 大数)
- JAVA学习笔记-01