实验二 动态规划算法 用动态规划法求解0/1背包问题-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

实验二 动态规划算法 用动态规划法求解0/1背包问题

简介:

  用动态规划法求解0/1背包问题

一、实验要求与目的

1、  掌握动态规划算法求解问题的一般特征和步骤。

2、  使用动态规划法编程,求解0/1背包问题。

二、实验内容

1、  问题描述:给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?

2、  算法描述。

三、源代码

importjava.util.*;

import java.io.*;

 

public class SF_01Beibao_fenzhifa {

public static void main(String[] args) {

              Scanner read=new Scanner(System.in);

              System.out.println("请输入背包的容量:");

              int c=read.nextInt();

              System.out.println("请输入物品的个数:");

              int n=read.nextInt();

              int w[]=new int[n];

              int v[]=new int[n];

              System.out.println("请输入物品的重量:");

              for (inti=0;i<n ;i++ )

              {

                     w[i]=read.nextInt();

              }

              System.out.println("请输入物品的价值:");

              for (inti=0;i<n ;i++ )

              {

                     v[i]=read.nextInt();

              }

 

System.out.println("最优值为:"+maximumJoy(w,v,c));

    }

public static intmaximumJoy(int[] lostHealth, int[] joy,int c){

returnZeroOneBag(lostHealth,joy,c);

    }

public static intZeroOneBag(int[] weight,int[] value,int bag){

int[] dp=new int[bag+1];

for(inti=0;i<weight.length;i++){

int lost=weight[i];

if(lost<bag+1){

for(int j=bag-lost;j>=0;j--){

dp[j+lost]=Math.max(dp[j+lost], dp[j]+value[i]);

                }

            }

        }

returndp[bag];

    }

}结果:

 本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/824845



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章