注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

Java如何使用递归解决0-1背包问题

JAVA相关 水墨上仙 3077次浏览 已收录 手机上查看

问题描述: 有N件物品和一个容量为V的背包。第i件物品的费用是c,价值是w。求解将哪些物品装入背包可 使这些物品的费用总和不超过背包容量,且价值总和最大。 转自:http://puffsun.iteye.com/blog/1286331

基本思路:  这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。&nbsp用子问题定义状态:即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则&nbsp其状态转移方程便是:f[v]=max{f[v],f[v-c]+w}。实现代码:

 * @author Sun Kui  
 */  
public class Knapsack {  
    public static void main(final String... args) {  
        int[] arr = new int[5];  
        arr[0] = 11;  
        arr[1] = 8;  
        arr[2] = 7;  
        arr[3] = 5;  
        arr[4] = 3;  
        Knapsack k = new Knapsack();  
        System.out.println(k.knapsack(arr, 0, 20, 20));  
    }  
  
    /** 
     *@param arr    all of items in knapsack 
     *@param start  the start item to be put into the knapsack 
     *@param left   the remaining capacity of knapsack 
     *@param sum    capacity of knapsack 
     */  
    public boolean knapsack(int[] arr, int start, int left, int sum) {  
  
        if (arr.length == 0) {  
            return false;  
        }  
  
        // start from the next item in original array  
        if (start == arr.length) {  
            int[] tempArr = new int[arr.length - 1];  
            for (int i = 0; i < tempArr.length; i++) {  
                tempArr[i] = arr[i + 1];  
            }  
            return knapsack(tempArr, 0, sum, sum);  
        } else if (arr[start] > left) {  
            return knapsack(arr, start + 1, left, sum);  
        } else if (arr[start] == left) {  
            for (int i = 0; i < start + 1; i++) {  
                // print the answer out  
                System.out.print(arr[i] + "\t");  
            }  
            System.out.println();  
            return true;  
        } else {  
            return knapsack(arr, start + 1, left - arr[start], sum);  
        }  
    }  
}  


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Java如何使用递归解决0-1背包问题
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……