涡阳哪里有做网站的/sem和seo是什么意思

题目链接：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]);elsedp[i][v] = dp[i-1][v];}}System.out.println(dp[N][V]);}}
}