动态规划常见问题

 1 //import java.util.ArrayList;
 2 import java.util.Arrays;
 3 
 4 public class Solution {
 5     public static int[][] Bag(int W,int N, int wt[],int val[]){
 6         //初始化dp数组-定义状态
 7         /*dp[i][w] 表?：对于前 i 个物品，当前背包的容量为 w 时，这种情况下可以装下的最?价值是 dp[i][w]*/
 8         int dp[][] = new int[N+1][W+1];
 9         for (int i = 0; i < dp.length; i++) {
10             Arrays.fill(dp[i],0);
11         }
12         //编写状态转移代码
13         for (int i = 1; i <= N; i++) {
14             for (int w = 1; w <= W; w++) {
15                 if(w - wt[i-1] < 0){//容量不够，此时不装
16                     dp[i][w] = dp[i-1][w];
17                 }else{//容量够，装入背包
18                     dp[i][w]=Math.max(dp[i-1][w],//如果你没有把这第 i 个物品装?背包
19                                       dp[i-1][w-wt[i-1]] + val[i-1]);//如果你把这第 i 个物品装?了背包
20                 }
21             }
22         }
23         //返回dp表
24         return dp;
25     }
26 
27     public static void main(String[] args) {
28         int wt[] = new int[]{2,1,3};
29         int val[] = new int[]{4,2,3};
30         int W = 4,N = 3;
31 
32         int res[][] = Bag(W,N,wt,val);
33         for (int i = 0; i < res.length; i++) {
34             System.out.println(Arrays.toString(res[i]));
35         }
36     }
37 }