0-1背包问题代码,Java代码库,德仔网

代码语言

代码分类

【Java】 0-1背包问题

作者:racoon / 发布于2011/10/26/ 787

个人作业，完成任务，但是有个问题没解决，就是选择问题，si没有确定，就是选择放入背包中的资源不能确定，问题一大就不行了

<div>/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package ozknapsackpro;</div>
import java.util.Arrays;
import java.util.Vector;</div>
<div>/**
*
* @author racoon
*/
public class OZKnapsackPro {</div>
<div> /**
 * @param args the command line arguments
 */
 public static void main(String[] args) {
 // TODO code application logic here
 final int C = 12;
 int s[] ={0,9,7,6,6,4};
 int v[] ={0,28,27,24,7,8};
 int [][]bv =new int[s.length][C+1];
 for (int i = 0; i < s.length; i++) {
 bv[i][0]=0;
 }
 for (int i = 0; i < C+1; i++) {
 bv[0][i]=0;
 }
 for (int i = 1; i < s.length; i++) {
 for (int j = 1; j < C+1; j++) {
 if (s[i]>j) {
 bv[i][j]=bv[i-1][j];
 }
 else {
 int m = bv[i-1][j];
 int n = bv[i-1][j-s[i]]+v[i];
 if(m>=n){
 
 bv[i][j]= m;
 }
 else{
 
 bv[i][j]= n;
 }
 }
 // System.out.println("bv["+i+"]["+j+"]="+bv[i][j]);
 }
 }
 System.out.println("最大价值为："+bv[s.length-1][C]);
 
 System.out.println("选择的: ");//想把选择的包也算出来，没实现。。
 /*int i=1,j=C;
 while(j>0 && i<s.length)
 {
 System.out.println("i="+i+" "+"j="+j);
 if(i==(s.length-1) && j>0 && bv[i][j]==v[i])
 {
 System.out.println("s"+i);
 j -= s[i];
 ++i;
 }
 if(bv[i+1][j] > bv[i][j])
 {
 System.out.println("s"+i);
 j -= s[i];
 ++i;
 }
 else{
 ++i;
 }
 }*/
</div>
<div>
 }
}
</div>

试试其它关键字

　背包问题　

同语言下

可能有用的

racoon贡献的其它代码(2)