0-1背包问题(回溯法)

0-1背包问题

在0 / 1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。 对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。 本题采用回溯法进行求解:

代码如下:

public class Package {

/**
 * @param args
 */
private int num=10;
int[] W={19,23,12,34,24,34,56,24,53,35};  //背包重量
int[] V={57,68,87,17,12,21,31,42,14,15};   //背包权值
private int[] a=new int[10];
int C=300;
static int MaxValue=0;                   //背包背的最大权值
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Package p=new Package();
    p.ReadData();
    p.Search(0);
    PrintMaxValue();
}
public void ReadData(){
    for(int i=0;i<num;i++){
        System.out.println("弟"+i+"的重量和价值是:"+W[i]+"   "+V[i]);
    }
}

public void Search(int m){
    if(m>=num){
        CheckMax();
    }
    else {
        a[m]=0;
        Search(m+1);
        a[m]=1;
        Search(m+1);
    }

}
public void CheckMax(){
    int Weight=0;
    int Value=0;
    for(int i=0;i<num;i++){             //判断是否到达上限

        if(a[i]==1){
        Weight=Weight+W[i];
        Value=Value+V[i];
        }
    }
    if(Weight<=C){
        if(Value>MaxValue){
            MaxValue=Value;
            System.out.println("最大价值是:"+MaxValue);
        }
    }
}
public static void PrintMaxValue(){
    System.out.println(" 最终的最大价值是:"+MaxValue);
}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据派THU

Python能让你上天?带你挖掘隐藏彩蛋~(附代码)

4604
来自专栏HansBug's Lab

1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

1638: [Usaco2007 Mar]Cow Traffic 奶牛交通 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

2957
来自专栏小樱的经验随笔

FZU 2167 大王叫我来巡山呐

Problem 2167 大王叫我来巡山呐 Accept: 931    Submit: 1405 Time Limit: 1000 mSec    Memo...

3609
来自专栏ml

HDUOJ----2512一卡通大冒险

一卡通大冒险 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

3519
来自专栏Vamei实验室

“不给力啊,老湿!”:RSA加密与破解

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

4581
来自专栏WOLFRAM

错觉艺术的巅峰,错觉图形大师M.C. Escher的不可能方块的可能模型

1823
来自专栏PPV课数据科学社区

趣文 | 程序员们,都进来看看编程语言之父都有谁

1、PHP PHP之父,Rasmus Lerdorf,1994年,为了要维护个人网页而制作的一个简单的用Perl语言编写的程序。这些工具程序用来显示 Rasmu...

3527
来自专栏HansBug's Lab

3361: [Usaco2004 Jan]培根距离

3361: [Usaco2004 Jan]培根距离 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 16  S...

3555
来自专栏Guangdong Qi

iOS 简单易懂的粒子效果

2513
来自专栏Vamei实验室

Python补充06 Python之道

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

1102

扫码关注云+社区

领取腾讯云代金券