牛客NC320 装箱问题【中等 动态规划，背包问题 C++/Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/d195a735f05b46cf8f210c4ad250681c

几乎完全相同的题目：
https://www.lintcode.com/problem/92/description

思路

动态规划都是递归递推而来。php答案是动态规划版本，递归版本有
测试用例超时，C++/.JAVA/GO 递归版本能通过所有测试用例

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param V int整型
     * @param num int整型vector
     * @return int整型
     */
    int boxin(int V, vector<int>& num) {
        int maxStore = dfs(num, 0, V);
        return V - maxStore;
    }

    int dfs(vector<int>& arr, int idx, int rest) {
        if (rest < 0) return -1;
        if (idx == arr.size()) {
            return 0;
        }

        int p1 = dfs(arr, idx + 1, rest);
        int p2 = 0;
        int next = dfs(arr, idx + 1, rest - arr[idx]);
        if (next != -1) {
            p2 = next + arr[idx];
        }

        if (p1 > p2) {
            return p1;
        }
        return p2;
    }
};

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param V int整型
     * @param num int整型ArrayList
     * @return int整型
     */
    public int boxin (int V, ArrayList<Integer> num) {
        int maxstore  = dfs(num, 0, V);
        return V - maxstore;
    }

    public int dfs(ArrayList<Integer> ll, int idx, int rest) {
        if (rest < 0)
            return -1;

        if (idx == ll.size()) {
            return 0;
        }

        int p1 = dfs(ll, idx + 1, rest);
        int p2 = 0;
        int next = dfs(ll, idx + 1, rest - ll.get(idx));
        if (next != -1) {
            p2 = next + ll.get(idx);
        }

        return Math.max(p1, p2);

    }
}

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param V int整型
 * @param num int整型一维数组
 * @return int整型
 */
func boxin(V int, num []int) int {
maxStore := dfs(num, 0, V)
	return V - maxStore
}

func dfs(num []int, idx int, rest int) int {
	if rest < 0 {
		return -1
	}

	if idx == len(num) {
		return 0
	}

	p1 := dfs(num, idx+1, rest)
	p2 := 0

	next := dfs(num, idx+1, rest-num[idx])

	if next != -1 {
		p2 = next + num[idx]
	}

	if p1 > p2 {
		return p1
	}
	return p2
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param V int整型 
 * @param num int整型一维数组 
 * @return int整型
 */
function boxin( $V ,  $num )
{
        $n = count($num);
    $dp=[];
    for($i=0;$i<=$n;$i++){
        for($j=0;$j<=$V;$j++){
            $dp[$i][$j] = 0;
        }
    }

    for($i=$n-1;$i>=0;$i--){
        for($rest = 0;$rest<=$V;$rest++){
            $p1 = $dp[$i+1][$rest];
            $p2 =0;
            $next = $rest-$num[$i] <0 ? -1: $dp[$i+1][$rest-$num[$i]];
            if($next!=-1){
                $p2 = $next+$num[$i];
            }
            $dp[$i][$rest] = $p1>$p2? $p1:$p2;
        }
    }

    return $V- $dp[0][$V];
}