学步园

/*<br /> 好久没有用java写了。代码写的好丑的，简单的0 - 1背包<br /> DP[i][j]表示前i个物品,背包容量为j的最优值</p> <p> 状态转移方程为<br /> DP[i][j] = max(DP[i-1][j] , DP[i-1][j-v[i]] + w[i]);</p> <p> 时间复杂度N*V , 空间复杂度N*V</p> <p> 所以伪代码如下:<br /> for i = 所有物品<br /> for j = V to v[i]<br /> dp[j] = max(dp[j] , dp[j-v[i]] + w[i]);</p> <p> 空间优化到一维V</p> <p> */<br /> import java.io.*;<br /> import java.util.*;</p> <p>public class Main<br /> {<br /> public static void main(String[] args)<br /> {<br /> Scanner cin = new Scanner(new BufferedInputStream(System.in));<br /> int t;<br /> t = cin.nextInt();<br /> //while(t--)<br /> for(int k = 1; k <= t; k++)<br /> {<br /> int n, v;<br /> int a[];<br /> a = new int [1000];<br /> int b[];<br /> b = new int [1000];<br /> n = cin.nextInt();<br /> v = cin.nextInt();<br /> for(int i = 1; i <= n; i++)<br /> {<br /> a[i] = cin.nextInt();//价值<br /> }<br /> for(int i = 1; i <= n; i++)<br /> {<br /> b[i] = cin.nextInt();//体积<br /> }<br /> int sum[];<br /> sum = new int [1000];<br /> int dp[][];<br /> dp = new int [1001][1001];<br /> for(int i = 0; i < 1001; i++)<br /> //for(int j = 0; j < 1001; j++)<br /> dp[0][i] = 0;<br /> // Arrays.fill(dp, (int)0);</p> <p> for(int i = 0; i <= v; i++)<br /> sum[i] = 0;</p> <p> for(int i = 1; i <= n; i++)<br /> for(int j = 0; j <= v; j++)<br /> {<br /> if(b[i] > j)<br /> {<br /> dp[i][j] = dp[i - 1][j];<br /> continue;<br /> }<br /> if(dp[i - 1][j] > dp[i - 1][j - b[i]] + a[i])<br /> dp[i][j] = dp[i - 1][j];<br /> else<br /> dp[i][j] = dp[i - 1][j - b[i]] + a[i];</p> <p> }</p> <p> for(int i = 1; i <= n; i++)<br /> for(int j = v; j >= b[i]; j--)<br /> {<br /> if(sum[j] < sum[j - b[i]] + a[i] )<br /> sum[j] = sum[j - b[i]] + a[i];<br /> //System.out.println(sum[j]);</p> <p> }</p> <p> //System.out.println(sum[v]);<br /> System.out.println(dp[n][v]);<br /> }</p> <p> }</p> <p>}<br />