• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

动态规划常见问题

开发技术 开发技术 2周前 (04-29) 5次浏览

1 0-1背包

 动态规划常见问题

 java代码:

动态规划常见问题动态规划常见问题

 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 }

View Code

 

结果:

动态规划常见问题

 


程序员灯塔
转载请注明原文链接:动态规划常见问题
喜欢 (0)