完全背包

cpp，完全背包模板

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param v int整型 
     * @param n int整型 
     * @param nums int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        // write code here
        vector<int> dp1(v + 1, 0), dp2(v + 1, -1);
        dp2[0] = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = nums[i][0]; j <= v; ++j) {
                dp1[j] = max(dp1[j], dp1[j - nums[i][0]] + nums[i][1]);
                if (dp2[j - nums[i][0]] >= 0) {
                    dp2[j] = max(dp2[j], dp2[j - nums[i][0]] + nums[i][1]);
                }
            }
        }

        int res1 = dp1[v];
        int res2 = dp2[v] >= 0 ? dp2[v] : 0;

        return {res1, res2};
    }
};

func knapsack( v int ,  n int ,  nums [][]int ) []int {
    dp,dp1 := make([]int, v + 1),  make([]int, v + 1)
    for tmpV := 1; tmpV <= v; tmpV++ { // 遍历容量v作为状态复用
        max, max1 := 0, 0
        for i := 1; i <= len(nums);i++ {
            iv := nums[i - 1][0]
            iw := nums[i - 1][1]

            if tmpV >= iv {
                // 1. 放入第i种物品刚好得到最大价值
                if max < dp[tmpV - iv] +iw { 
                    max = dp[tmpV - iv] +iw
                }
                //2 第j种物品刚好填满i个容量 得到最大价值
                if (tmpV - iv == 0 || dp1[tmpV - iv] != 0) && max1 < dp1[tmpV - iv] + iw { 
                    max1 = dp1[tmpV - iv] + iw
                }
            } 
        }
        dp[tmpV], dp1[tmpV] = max, max1
    }
    return []int{dp[v], dp1[v]}
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param v int整型 
     * @param n int整型 
     * @param nums int整型ArrayList<ArrayList<>> 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        // write code here
        ArrayList<Integer> al = new ArrayList<Integer> ();
        int[] dp = new int[v+1];
        int[] dpl = new int[v+1];
        dp[0] = 0;
        Arrays.fill(dpl,Integer.MIN_VALUE);
        dpl[0] = 0;
        for(int curHeave = 1;curHeave <= v;curHeave++){
            for(int i = 0;i<n;i++){
                int k = curHeave  - nums.get(i).get(0);
                if(k < 0) continue;
                else{
                if(dpl[k] == Integer.MIN_VALUE);
                else{dpl[curHeave] = Math.max(dpl[curHeave],dpl[k]+nums.get(i).get(1));}
                dp[curHeave] = Math.max(dp[curHeave],dp[k]+nums.get(i).get(1));
                }
                
            }
        }
        al.add(dp[v]);
       if(dpl[v] == Integer.MIN_VALUE){
           al.add(0);
       }else{
           al.add(dpl[v]);
       }
        return al;
    }
}