一维优化+y氏分析法(Java)
Java 代码
import java.io.*;
public class Main {
static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static final int V = 10010, N = 26;
static long[] f = new long[V];
static int[] w = new int[N];
static int n, v;
public static void main(String[] args) throws Exception {
n = getInt(); v = getInt();
for (int i = 0; i < n; i++) {
w[i] = getInt();
}
/*
n种物品,每种物品价值、体积均为wi。每种物品可选无限次。
要求选出物品总价值恰为v的方案数
*/
f[0] = 1; // 什么都不选有1种方案
for (int i = 0; i < n; i++) {
int wi = w[i];
for (int j = 0; j <= v; j++) {
if (j - wi >= 0 && j - wi <= v) {
f[j] += f[j - wi];
}
}
}
pw.println(f[v]);
pw.flush();
}
public static int getInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
}