解题思路: 二维数组递归,01背包问题
注意事项: dp[i][j]为只用前i个箱子(包含第i个)在不超过j体积下的最大利用空间
参考代码:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int V = scanner.nextInt();
int N = scanner.nextInt();
int vs[] = new int[N+1];
int dp[][]= new int[N+1][V+1];
for(int i=1;i<=N;i++){
vs[i]=scanner.nextInt();
}
for(int i=1;i<=N;i++){
for(int j=1;j<=V;j++)
if(j-vs[i]>=0)//可以放下第i个箱子
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-vs[i]]+vs[i]);
else dp[i][j]=dp[i-1][j];//放不下第i个箱子
}
System.out.println(V-dp[N][V]);
}
}
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:763 |
计算质因子 (C++代码)浏览:1641 |
简单的a+b (C语言代码)浏览:692 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:337 |
1642题解浏览:715 |
Minesweeper (C语言描述,蓝桥杯)浏览:1126 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:1918 |
震宇大神的杀毒软件 (C语言代码)浏览:1080 |
C语言程序设计教程(第三版)课后习题12.5 (C语言代码)浏览:766 |
C语言训练-排序问题<1> (C语言代码)浏览:355 |