题目描述

背包DP

推荐题解
作者： 林小鹿
链接： https://www.acwing.com/solution/content/30622/

无优化

import java.util.*;

public class Main{
    static int N = 30,M = 10010; 
    static int n, m; 
    static long[][] f = new long[N][M];
    static int[] w = new int[N];


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n ; i++){
            w[i] = sc.nextInt();
        }

        //金额为0 有一种方案 就是啥都不选
        f[0][0] = 1;
        //枚举货币种类
        for (int i = 1; i <= n; i ++ )
        {
          //枚举每个金额
          for(int j = 0; j <= m; j++){
            //枚举当前使用几个当前种类的货币
            for(int k = 0; w[i] * k <= j; k++){
                //f[i-1][j - k * w[i]]
                f[i][j] = f[i][j] + f[i - 1][j - k *w[i]];
            }
          }
        }

        System.out.println(f[n][m]);
    }
}

有优化

import java.util.*;

public class Main{
    static int M = 10010; 
    static int N = 30;
    static int n, m; 
    static long[][] f = new long[N][M];
    static int[] w = new int[N];


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n ; i++){
            w[i] = sc.nextInt();
        }

        //金额为0 有一种方案 就是啥都不选
        f[0][0] = 1;
        //枚举货币种类
        for (int i = 1; i <= n; i ++ )
        {
          //枚举每个金额
          for(int j = 0; j <= m; j++){
             f[i][j] = f[i - 1][j];
             if(j >= w[i]) f[i][j] += f[i][j - w[i]];
          }
        }
        System.out.println(f[n][m]);
    }
}