牛客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 := 0next := 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];
}