用动态规划法求解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