牛牛的背包问题

import java.util.*;
public class Main{
    static int count = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] v = new int[n];
        long sum = 0;
        count = 0;
        for (int i = 0;i < n;i ++){
            v[i] = sc.nextInt();
            sum += v[i];
        }
        if (sum <= w){
            System.out.println((int)Math.pow(2,n));
        }else {
            dfs(0,0,n,v,w);
            System.out.println(count + 1);
        }
    }
    public static void dfs(long cursum,int index,int n,int[] v,int w){
        if (index < n){
            if (cursum > w){
                return;
            }
            //不包含当前零食
            dfs(cursum,index + 1,n,v,w);
            if (cursum + v[index] <= w){
                //包含当前零食，计数+1，当前总数增加
                count ++;
                dfs(cursum + v[index],index + 1,n,v,w);
            }
        }
    }
}

/*

 */
package main

import "fmt"
import "math"
var count=1
func main() {
    var n,w int
    fmt.Scan(&n,&w)
    data:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scan(&data[i])
    }
    maxSum:=0
    for i:=0;i<n;i++{
        maxSum+=data[i]
    }
    if maxSum<w{
        fmt.Println(int(math.Pow(2,float64(n))))
        return 
    }
    robot(0,n,w,data)
    fmt.Println(count)
}
func robot(idx int,n int,w int,data[]int){
    if idx>=n{
        return
    }
    robot(idx+1,n,w,data)
    if(w-data[idx]>0){
        count++
        robot(idx+1,n,w-data[idx],data)
    }

}

package p2;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BackPack {
 //
    //记录下w下的子问题的值，以便下次遇到直接使用，而不用再算一次
    private static Map<Long, Long> flag = new HashMap<>();
    public static long find(int n,long w,long[] v,long all){
        
        
        
        if(n<0)
            return 1;
        Long temp=flag.get(w);
        if(temp!=null){
        
            return temp;
            
        }
        
        long tem1 = 0;
        long tem2=0;
        if(w+v[n]<=all){
        tem1=find(n-1,w+v[n],v,all); //要么放w+相应体积
        }
            
        tem2=find(n-1,w,v,all);//要么不放

        flag.put(w, (tem1+tem2));
        return flag.get(w);

    }
    public static void main(String[] arg){
        
        Scanner scan=new Scanner(System.in);
        int num=scan.nextInt();long all=scan.nextInt();
    
        long[] v=new long[num];
        long x=0;
        for(int i=0;i<num;i++){
            
        v[i]=scan.nextInt();
            x=v[i]+x;
        }
        //如果零食总和加起来还没有背包重，那么算法就是问题下面的示例那种算法
        if(x<all){
            x=1;
            for(int i=0;i<num;i++)
                x=2*x;
        System.out.println(x);
        }else
        System.out.println(find(num-1,0,v,all));
    
    }
}