24,[8,3,12,7,9,7]
0
public int boxin (int V, ArrayList<Integer> num) { // write code here boolean[] dp = new boolean[V+1]; dp[0] = true; for(int x : num) { for(int i = V; i >= x; --i) { dp[i] = dp[i] || dp[i-x]; } } int m = V; while(!dp[m]) { --m; } return V - m; }
解题思路:
这题与0-1背包问题很相似,能不能直接套用公式?但似乎缺少价值这一参数,以及要求解空间最小
0-1背包追求价值最大,如何设置适当的价值使问题转化?注意到 V - minV是背包中已被占用的最大空间,若用这些空间表示价值,就变成了0-1背包问题
V - minV
令w=n,c=n求解0-1背包解res,该问题就是V-res
w=n,c=n
V-res
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题