基本题二：0—1背包问题

 

一、实验目的与要求

1、掌握0—1背包问题的回溯算法；

2、进一步掌握回溯算法；

二、实验题：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

三、实验提示

template<class Typew, class Typep>

Typep Knap<Typew, Typep>::Bound(inti)

{// 计算上界

   Typew cleft = c - cw;  // 剩余容量

   Typep b = cp;

   // 以物品单位重量价值递减序装入物品

   while (i<= n && w[i] <= cleft) {

      cleft -= w[i];

      b += p[i];

      i++;

      }

   // 装满背包

   if (i<= n) b += p[i]/w[i] * cleft;

   return b;

}

 

四、源代码

importjava.util.*;

import java.io.*;

 

importjavax.swing.*;

importjava.lang.*;

public class SF_Beibao_01_01{

 

public static void main(String[] args) {

              Scanner read=new Scanner(System.in);

 

System.out.print("输入背包容量：");

              int c=read.nextInt();

System.out.print("物品个数：");

              int n1=read.nextInt();

              //构建数组

              int [][]m=new int [n1][c+1];

              int []v=new int[n1];

              //数组赋值及输出

              System.out.println("物品价值数组：");

              for(inti=0;i<n1;i++){

                     v[i]=read.nextInt();

              }

              System.out.println();

              int []w=new int[n1];

              //数组赋值及输出

              System.out.println("物品质量数组：");

              for(inti=0;i<n1;i++){

                     w[i]=read.nextInt();

              }

              System.out.println();

 

              knapsack(v,w,c,m);

              System.out.println("输出0-1背包问题的最优解"+m[1][c]);

 

       }

    public static void knapsack(int[]v,int[]w,intc,int[][]m){

              int n=v.length-1;

              intjMax=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(inti=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]);

 

              }

    public static void trackback(int[][]m,int[]w,intc,int[]x){

              int n=w.length-1;

              for(inti=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;

    }

}

 

输入：

背包容量：10

物品个数：5

物品价值：6 3 5 4 6

物品质量：2 2 6 5 4

结果：

 

本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/824856