0-1背包问题 为什么有错?
package com.sohu;public class question0_1 {
public static int[][] knapsack(int[]v,int[]w,int c,int[][]m){
int n=v.length-1;
int jMax=Math.min(w[n]-1, c);
for(int j=0;j<=jMax;j++){
m[n][j]=0;
}
for(int j=w[n];j<=c;j++){
m[n][j]=v[n];
}
for(int i=n-1;i>1;i--){
jMax=Math.min(w[i]-1, c);
for(int j=0;j<=jMax;j++){
m[i][j]=m[i+1][j];
}
for(int j=w[i];j<=c;j++){
m[i][j]=Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=Math.max(m[1][c], m[2][c-w[1]]+v[1]);
}
return m;
}
/*public static void traceback(int[][]m,int[]w,int c,int[]x){
int n=w.length-1;
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c])
x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]>0?1:0);
}
*/
public static void main(String[]args){
int c=10;
int[] w={2,2,6,5,4};
int[] v={6,3,5,4,6};
int[][] m=new int[w.length][c];
knapsack(v,w,c,m);
for(int i=w.length-1;i>=0;i--)
for(int j=0;j<c;j++)
System.out.println(m[i][j]+"\n");
}}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at com.sohu.question0_1.knapsack(question0_1.java:11)
at com.sohu.question0_1.main(question0_1.java:46)
package com.sohu;public class question0_1 {
public static int[][] knapsack(int[]v,int[]w,int c,int[][]m){
int n=v.length-1;
int jMax=Math.min(w[n]-1, c);
for(int j=0;j<=jMax;j++){
m[n][j]=0;
}
for(int j=w[n];j<=c;j++){
m[n][j]=v[n];
}
for(int i=n-1;i>1;i--){
jMax=Math.min(w[i]-1, c);
for(int j=0;j<=jMax;j++){
m[i][j]=m[i+1][j];
}
for(int j=w[i];j<=c;j++){
m[i][j]=Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=Math.max(m[1][c], m[2][c-w[1]]+v[1]);
}
return m;
}
/*public static void traceback(int[][]m,int[]w,int c,int[]x){
int n=w.length-1;
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c])
x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]>0?1:0);
}
*/
public static void main(String[]args){
int c=10;
int[] w={2,2,6,5,4};
int[] v={6,3,5,4,6};
int[][] m=new int[w.length][c];
knapsack(v,w,c,m);
for(int i=w.length-1;i>=0;i--)
for(int j=0;j<c;j++)
System.out.println(m[i][j]+"\n");
}}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at com.sohu.question0_1.knapsack(question0_1.java:11)
at com.sohu.question0_1.main(question0_1.java:46)
可是还是有错误
at com.sohu.question0_1.knapsack(question0_1.java:21)
at com.sohu.question0_1.main(question0_1.java:46)
public class question0_1 {
public static int[][] knapsack(int[]v,int[]w,int c,int[][]m){
int n=v.length-1;
int jMax=Math.min(w[n]-1, c);
for(int j=0;j<jMax;j++){
m[n][j]=0;
}
for(int j=w[n];j<c;j++){
m[n][j]=v[n];
}
for(int i=n-1;i>1;i--){
jMax=Math.min(w[i]-1, c);
for(int j=0;j<jMax;j++){
m[i][j]=m[i+1][j];
}
for(int j=w[i];j<c;j++){
m[i][j]=Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
m[1][c-1]=m[2][c-1];
if(c>=w[1])
m[1][c-1]=Math.max(m[1][c-1], m[2][c-w[1]]+v[1]);
}
return m;
} /*public static void traceback(int[][]m,int[]w,int c,int[]x){
int n=w.length-1;
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c])
x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]>0?1:0); }
*/
public static void main(String[]args){
int c=10;
int[] w={2,2,6,5,4};
int[] v={6,3,5,4,6};
int[][] m=new int[w.length][c];
knapsack(v,w,c,m);
for(int i=w.length-1;i>=0;i--)
for(int j=0;j<c;j++)
System.out.println(m[i][j]+"\n");
} }
一、 JAVA基础培训
1. 孙鑫Java无难事(共108集)
本套光盘由孙鑫老师亲自授课录制。内容涵盖面广,从入门到精通,授课通俗易懂,分析问题独到精辟,学员通过本套光盘的学习,能够快速掌握Java编程语言,成为Java高手。
2. 张孝祥Java就业培训(共56集)
本套教学光盘深入浅出的理论分析、精练生动的案例讲解、亲切直观的操作界面、恍然大悟的学习收获。张孝祥老师的课程,就不用多说了。
3. 翁凯Java语言视频培训(共30集)
本视频教学是由浙江大学著名年轻计算机专家翁恺教授主讲,一共30集,讲得很好,从JAVA的基础讲起,由浅入深,绝对是精品。看本视频讲座最好是有一点c++的底子
二、 JAVA进阶培训
1. 赛迪网校J2EE软件工程师培训(J2EE基础13集 高级17集 案例7集)
本课程包括J2EE的各个主要方面,以及开发环境,设计模式,和经典案例分析等实用内容。通过本课程的学习,学员将具有J2EE开发的扎实理论基础和实际设计经验,可胜任企业级应用的设计和开发等实际工作。本课程共计约40课时。授课教师均是来自主流J2EE厂商并具有J2EE 5年以上开发和咨询经验的技术专家。
2. J2EE Web程序开发(共38集)
国内最知名的J2EE讲师刘晓涛讲师执教,课程生动形象并结合典型企业案例深入的分析。从零开始:该课程以零基础为起点,强调基础理论结合实际;以基础理论课程为第一阶段,到常用工具使用及工作应用为提高部分。专业性强:多平台软件开发(Windows/Linux) ;紧跟先进的技术(极限编程/测试驱动开发);规范化(学习印度软件经验);不仅仅是编程,在教学过程当中渗透设计思想;编程思想的熏陶,打通任督二脉,对编程语言一通百通;软件工程思想的灌输(分析,设计,实现,测试一条龙)。
三、 JAVA实战项目培训录像
该培训录像是北京尚学堂科技第一个项目(聊天系统)和 第二个项目(坦克大战)的课堂实录,马士兵老师以手把手一行一行代码的形式教大家如何开发一个示例性Chat和一个相当完备的TankWar游戏,详尽透彻的解释了j2se的常用知识,只要按照教程中的操作一步一步完成,你就足以掌握j2se/eclipse到能够进一步学习的水平了,项目实战,不容错过!
四、 Oracle 9i 大型视频培训录像(共64集,13.4G)
*1Z0-007 Introduction to Oracle9i SQL
*1Z0-031 Oracle9i DBA Fundamentals I
*1Z0-032 Oracle9i DBA Fundamentals II
*1Z0-033 Oracle9i Performance Tuning
另附全套PPT培训讲稿。联系方式:
QQ:421130479
MSN:[email protected]
Tel:13512510369(短信佳)
E-mail:[email protected]