使用动态规划,dp[i]记录当容积为i时的最大填充体积
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int capacity=sc.nextInt(),n=sc.nextInt();
int[]objs=new int[n];
for(int i=0;i<n;i++)
objs[i]=sc.nextInt();
int[]dp=new int[capacity+1];
Arrays.fill(dp,0);
for(int i=0;i<n;i++){
for(int j=capacity;j>=objs[i];j--){
dp[j]=Math.max(dp[j],dp[j-objs[i]]+objs[i]);
}
}
System.out.println(capacity-dp[capacity]);
}
}
例
当输入为10 3 4 5 8时dp数组的变化(即箱子容积为10,有三个物体,体积分别为4,5,8)
dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] | dp[8] | dp[9] | dp[10] |
---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
0 | 0 | 0 | 0 | 4 | 5 | 5 | 5 | 5 | 9 | 9 |
0 | 0 | 0 | 0 | 4 | 5 | 5 | 5 | 8 | 9 | 9 |
两层循环:
- 外层表示本轮使用第i个物体
- 内层表示用该物体填充各种最大容积情况下的容器
dp[j]=Math.max(dp[j],dp[j-objs[i]]+objs[i]);
表示从以前的最大填充体积,和放入该物体后的最大填充体积中选取大的那个。dp[j-objs[i]]+objs[i]
表示:除去该物体的体积后,剩下的容积在以前的情形下的最大填充体积 + 该物体的体积
每一轮循环(从dp[10]到dp[objs[i]] )放入物体,务必从右往左,因为从右往左参考的小的dp值是上一轮的,即参考的是以前放入物品后形成的最大填充体积,而从左往右会导致参考的dp值有可能已受本轮物品的影响,则造成二次放入,故for(int j=capacity;j>=objs[i];j--)
必须这样写
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)