＜动态规划＞完全背包(最大价值，恰好装满最大价值)

106 阅读 0 评论 70 点赞

我是靠谱客的博主忧郁招牌，这篇文章主要介绍＜动态规划＞完全背包(最大价值，恰好装满最大价值)，现在分享给大家，希望可以做个参考。

完全背包_牛客题霸_牛客网 (nowcoder.com)

(10条消息) 01背包完全背包是否恰好装满问题_Simple的博客-CSDN博客

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        int[] dp = new int [v+1];
        int[] dp1 = new int[v+1];
        for(int i = 0;i<dp1.length;i++){
            dp1[i] = -1;
        }
        dp1[0] = 0;

        for(int i = 0;i<n;i++){
            for(int j = nums.get(i).get(0);j<=v;j++){
                dp[j] = Math.max(dp[j],dp[j-nums.get(i).get(0)]+nums.get(i).get(1));
                if(dp1[j-nums.get(i).get(0)]!=-1){
                    dp1[j] = Math.max(dp1[j],dp1[j-nums.get(i).get(0)]+nums.get(i).get(1));
                }
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        res.add(dp[v]);
        res.add(dp1[v]==-1?0:dp1[v]);
        return res;
    }