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

java 代码

/**
 *
 */
package com.zyf;

/**
 * @author zyf 题目：给定n个物体，其中第i个物体重量wi，价值vi ，另有一个最大载重W的背包，往里面塞东西使得总价值尽可能大
 *
 * 令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值
 * f(i,j)=max{f(i-1,j), f(i-1, j-w[i])+v[i] } ,i>0, j>=w[i];
 * f(i,j) = f(i-1,j) , i>0, j<w[i];
 * f(0,j) = v[0] , i=0, j>=w[0];
 * f(0,j) = 0, i=0, j<w[0];
 *
 */
public class bagPro {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO 自动生成方法存根


        int w[] = {2,2,6,5,4};
        int v[] = {6,3,5,4,6};
        int c = 10;
        int f[][] = new int [5][c+1];

        int maxValue = 0;

        for(int j=0 ; j<=c; j++){
            if(j>=w[0])
                f[0][j] =v[0];
            else
                f[0][j] = 0;
        }

        for(int i=1; i<w.length; i++){
            for(int j=0; j<=c;j++){
                if(j<w[i])
                    f[i][j] = f[i-1][j];
                else if(f[i-1][j]>=f[i-1][j-w[i]]+v[i])
                    f[i][j] = f[i-1][j];
                else
                    f[i][j] = f[i-1][j-w[i]]+v[i];
            }
        }

        System.out.println(f[4][c]);




    }
}

分享到：

solaris下vi的使用（转） | 数据库范式（转）

• 2007-06-19 22:35
• 浏览 3801
• 评论(0)
• 查看更多