소 가방 문제 - 01 가방 문제

1 소 가방 문제
소 와 소의 배낭 문제 - 소 객 망 문제 설명: 소 와 소 는 학교 에서 조직 한 봄 여행 에 참가 하려 고 한다. 출발 하기 전에 소 와 소 는 가방 에 간식 을 넣 으 려 고 한다. 소의 가방 용량 은 w 이다.
소 와 소의 집 에는 모두 n 봉지 의 간식 이 있 는데, i 봉지 의 간식 부 피 는 v [i] 이다.
소 와 소 는 총 부피 가 가방 용량 을 초과 하지 않 는 상황 에서 그 가 모두 몇 가지 간식 을 넣 는 지 알 고 싶 어 한다.
입력 설명: 두 줄 의 첫 번 째 행동 두 개의 정수 n 과 w (1 < = n < = 30, 1 < = w < = 2 * 10 ^ 9) 를 입력 하여 간식 의 수량 과 가방 의 용량 을 표시 합 니 다.두 번 째 줄 n 개의 정수 v [i] (0 < = v [i] < = 10 ^ 9) 는 간식 한 봉지 의 부 피 를 나타 낸다.
2 프로 그래 밍 실현

package com.cow;

import java.util.Scanner;

/*
21 1165911996
842104736 130059605 359419358 682646280 378385685 622124412 740110626 814007758 557557315 40153082 542984016 274340808 991565332 765434204 225621097 350652062 714078666 381520025 613885618 64141537 783016950
*/
public class Cow {
	private static int methodNum = 0;
	public static void main(String[] args) {
		int n;
		Long w;//  ：       N   ，       int  。
		Scanner input = new Scanner(System.in);
		n = input.nextInt();
		w = input.nextLong();

		input.nextLine();//            ，    。          
		String line = input.nextLine();//        ，     
		input.close();
		
		String[] splitLine = line.split(" ");
		
		int[] v = new int[n+1];
		Long total = 0L;
		for (int i = 0; i < splitLine.length; i++) {
			v[i + 1] = Integer.parseInt(splitLine[i]);
			total += v[i + 1];
		}
		
		if(total <= w) methodNum = (int) Math.pow(2, n);
		else {
			calMethodNum(n,w,v,0L,1); //        0，        1 
		}
		System.out.println(methodNum);
	}
	
	private static void calMethodNum(int n, Long w, int[] v,Long sum,int loc) {
		if(sum > w) {
			return;
		}
		
		if(sum <= w) {
			methodNum ++;
		}
		
		for(int i=loc;i<=n;i++) {//   i          ，     。
			if(w - sum > v[i]) {//              i      ，       。
				calMethodNum(n, w, v, sum + v[i], i+1);
			}
			//   if  ，     i+1   ，         。  if ，           i 。
		}
	}
}