2013
12-12

# 九度-1114-神奇的口袋[解题代码]

3
20
20
20

3

cpp 代码如下：
#include <iostream>
using namespace std;
int arr[21],n;
int ans;
int bfs(int index,int sum){
//cout << index << " " << sum <<endl;
if(sum == 0){
return 1;
}
if(index == n || sum < 0)
return 0;
return bfs(index +1, sum) + bfs(index +1, sum - arr[index]);

}

int main()
{

while(cin >> n){
for(int i=0; i<n; i++)
cin >> arr[i];
ans = 0;
ans = bfs(0,40);
cout << ans << endl;
}
return 0;
}
/**************************************************************
Problem: 1114
User: coder
Language: C++
Result: Accepted
Time:0 ms
Memory:1520 kb
****************************************************************/

java 代码如下：

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
static int n;
static int arr[];
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while(s.hasNextInt()){
n = s.nextInt();
arr = new int[n];
for(int i=0;i<n; i++)
arr[i] = s.nextInt();

System.out.println(f(n-1,40));
}

}

static int f(int n,int sum){
if(sum < 0)
return 0;
if(sum == 0)
return 1;
if(n==0)
return arr[0] == sum ? 1:0;
else
return f(n-1,sum)+f(n-1,sum-arr[n]);
}

}
/**************************************************************
Problem: 1114
User: coder
Language: Java
Result: Accepted
Time:120 ms
Memory:18844 kb
****************************************************************/

1. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了

2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮