动态规划求0-1背包问题

问题描述

小偷发现了n个商品，第i个商品重量为w_i,价值为v_i。小偷希望尽量拿走价值高的商品，但是他的背包只能容纳W重的商品。求如何取舍这些商品？ 由于对一个商品，要么被拿走要么不被拿走，所以被称为0-1背包问题。

求解思路

令m[i][j]表示第1个商品到第i个商品中，背包容量为j的情乱下，可获得的最大价值；
决定是否选择商品的方案，比较选与不选获得的价值大小,所以有递推式：
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]+v[i]]) 当 j>=w[i]时
m[i][j]=m[i-1][j] 当 j<w[i]时

代码求解

import java.util.Scanner;
public class BagProblem {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int[] value = new int[6];
        int[] weight = new int[6];
        value[0]=0;
        weight[0]=0;
        int i,j;
        String[] str1 = scan.nextLine().split(",");
        String[] str2 = scan.nextLine().split(",");     
        for(i=0;i<5;i++){
            value[i+1]=Integer.parseInt(str1[i]);   
        }
        for(j=0;j<5;j++){
            weight[j+1]=Integer.parseInt(str2[j]);      
        }
        int capacity = Integer.parseInt(scan.nextLine());
        int[][] m = new int[6][capacity+1];
        for(i=0;i<6;i++){
            for(j=0;j<=capacity;j++)
                m[i][j]=0;
        }
        for(i=1;i<=5;i++){
            for(j=1;j<=capacity;j++){
                if(weight[i]>j){
                    m[i][j]=m[i-1][j];
                }
                else{
                    m[i][j]=Math.max(m[i-1][j],m[i-1][j-weight[i]]+value[i]);
                }
            }
        }
        System.out.println(m[5][capacity]);
        traceback(5,weight,m,capacity);
        }
      public static void traceback(int n,int[]w,int[][]m,int c){
        int[] x = new int[n+1];
        for(int i=5;i>1;i--){
            if(m[i][c]==m[i-1][c])
                x[i]=0;
            else{
                x[i]=1;
                c-=w[i];
            }
        }
        x[1]=(m[1][c]>0)?1:0;
        for(int j=1;j<=n;j++)
            System.out.print(x[j]+" ");
    }
}