题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602
思路分析：该问题为经典的0-1背包问题；假设状态dp[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值，则可以推导出dp递推公式
dp[i][v] = Max{dp[i-1][v], dp[i-1][v – c[i]] + w[i]}；c[i]表示第i件物品的容量，w[i]表示第i件物品的价值；该动态规划问题每个阶段的决策为是否要
选择第i件物品放入背包中，如果不选择第i件物品，则dp[i][v] = dp[i-1][v]，如果选择第i件物品放入背包，则dp[i][v] = dp[i-1][v-c[i]], v-c[i] >= 0；
同时，可以使用一维数组递推，因为递推i时，只需要使用到第i-1行的数组元素，所以可以从V向下递推到0，递推公式如下： dp[v] = MAX(dp[v], dp[v - c[i]] + w[i])，
(一维dp)代码如下：
import java.util.*;
public class Main {
static final int MAX_N = 1000 + 10;
static int[] value = new int[MAX_N];
static int[] volumn = new int[MAX_N];
static int[] dp = new int[MAX_N];
public static int Max(int a, int b) {
return a > b ? a : b;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int case_times = in.nextInt();
while (case_times-- != 0) {
int N, V;
for (int i = 0; i < MAX_N; ++ i)
dp[i] = 0;
N = in.nextInt();
V = in.nextInt();
for (int i = 1; i <= N; ++ i)
value[i] = in.nextInt();
for (int i = 1; i <= N; ++ i)
volumn[i] = in.nextInt();
for (int i = 1; i <= N; ++ i) {
for (int v = V; v >= 0; -- v) {
if (v - volumn[i] >= 0)
dp[v] = Max(dp[v], dp[v - volumn[i]] + value[i]);
}
}
System.out.println(dp[V]);
}
}
}
(二维dp)代码如下：
import java.util.*;
public class Main {
static final int MAX_N = 1000 + 10;
static int[] value = new int[MAX_N];
static int[] volumn = new int[MAX_N];
static int[][] dp = new int[MAX_N][MAX_N];
public static int Max(int a, int b) {
return a > b ? a : b;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int case_times = in.nextInt();
while (case_times-- != 0) {
int N, V;
for (int i = 0; i < MAX_N; ++ i) {
for (int j = 0; j < MAX_N; ++ j)
dp[i][j] = 0;
}
N = in.nextInt();
V = in.nextInt();
for (int i = 1; i <= N; ++ i)
value[i] = in.nextInt();
for (int i = 1; i <= N; ++ i)
volumn[i] = in.nextInt();
for (int i = 1; i <= N; ++ i) {
for (int v = 0; v <= V; ++ v) {
if (v - volumn[i] >= 0)
dp[i][v] = Max(dp[i-1][v], dp[i-1][v - volumn[i]] + value[i]);
else
dp[i][v] = dp[i-1][v];
}
}
System.out.println(dp[N][V]);
}
}
}