动态规划之0-1背包问题 java_0-1背包实验目的

动态规划之0-1背包问题

一、实验目的

1.进一步理解动态规划法思想；
2.进一步掌握动态规划法步骤；
3.学会使用动态规划算法实现0-1背包；
4.学会使用动态规划算法实现最大子序和。

二、实验内容

1.问题描述
题目：
给定N个物品，每一个物品有一个重量W和一个价值V。你有一个能装M重量的背包，问怎么装使得装价值最大。每一个物品只有一个。
输入格式
输入的第一行包含两个整数n,m，分别表示物品的个数和背包能装载重量。
以后N行每行两个数w和v，表示物品的重量和价值
输出格式
输出一行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
1<=N<=200,M<=5000.
2.要求
（1）写出问题分析过程
（2）写出程序代码
（3）贴出程序结果

实验过程

（1）分析
面对每一个物品，我们只有选择拿或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。
c[]代表每个物品体积，w[]代表每个物品的价值
设f[i][j]代表前i件物品放入容量为j的背包的最大价值。
①j<=c[i]的情况，这时候背包容量不足以放下第n件物品，只能选择拿或者不拿f[i][j]=f[i-1][j]

②j>=c[i]的情况，这时背包可以容纳下第i件物品；如果拿取，f[i][j]=f[i-1][j-c[i]]+w[i]
如果不拿，f[i][j]=f[i-1][j]
究竟拿还是不拿，自然是比较这两种情况那种价值最大。

（2）程序代码

package ch01;

import java.util.Scanner;

public class bag {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int V = scanner.nextInt();
		int [] v = new int [N+1];
		int [] w = new int [N+1];
		for(int i=0;i<N;i++)
		{
			v[i] = scanner.nextInt();
			w[i] = scanner.nextInt();
		}
		System.out.println(cal(N,V,w,v));

	}
	/*
	 * n  物品个数
	 * v  背包总容量
	 * w  每一个物品的价值，注意下标从1开始
	 * c  每一个物品的体积，下标从1开始
	 */
	private static int cal(int n,int v,int [] w,int [] c) {
		if(n==0||v==0) return 0;
		if(w == null||w.length == 0) return 0;
		if(c == null || c.length == 0) return 0;
		
		int [][] f= new int [n+1][v+1];
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=v;j++)
			{
				f[i][j] = j<c[i]?f[i-1][j]:Math.max(f[i-1][j], f[i-1][j-c[i]]+w[i]);
				
			}
		}
		return f[n][v];
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

（3）运行结果