美文网首页
背包问题

背包问题

作者: nafoahnaw | 来源:发表于2018-06-14 19:57 被阅读0次
    /**
     * 有n个重量和价值分别为Wi,Vi的物品。
     * 从这些物品中挑选出总重量不超过W的物品,求所有有挑选方案中价值总和的最大值
     * @author haofan.whf
     * @version $Id: Bag01.java, v 0.1 2018年06月14日 下午7:26 haofan.whf Exp $
     */
    public class Bag01 {
    
        //物品数量
        int n = 4;
    
        //背包容量
        int W = 5;
    
        //物品重量
        int[] WArray = new int[]{2,1,3,2};
    
        //物品价值
        int[] VArray = new int[]{3,2,4,2};
    
        //用数组来存储已经被计算过的值,用来剪枝
        int[][] dp = new int[n+1][W+1];
        
        {
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp[i].length; j++) {
                    dp[i][j] = -1;
                }
            }
        }
    
        //从第i个物品开始挑选总重量<j的部分
        public int solution(int i, int j){
            //当已经得知计算的结果时,直接返回
            if(dp[i][j] >= 0){
                return dp[i][j];
            }
            int res = 0;
            if(i == n){
                //已经没有剩余的物品了
                res = 0;
            }else if(j < WArray[i]){
                //当前物品放不下,移至下一个物品
                res = solution(i + 1, j);
            }else{
                //如果能放下则放/不放两种场景都需要计算,并取得最大值
                res = Math.max(solution(i + 1, j - WArray[i]) + VArray[i]
                        , solution(i + 1,j));
            }
            dp[i][j] = res;
            return res;
        }
    }
    

    相关文章

      网友评论

          本文标题:背包问题

          本文链接:https://www.haomeiwen.com/subject/hokueftx.html