蓝桥杯算法提高VIP-01背包 （Java代码）

解题思路:
解决背包问题，首先要看通俗背包如何解决，0-1背包为全背包中一种比较特殊的背包问题。区别于单个物品的取出问题。下面将黏贴两份代码，分别为全背包问题的代码以及0-1背包的问题代码。

值得说的是背包问题实质是动态规划的典型问题，需要了解动态规划的两个特征1。子问题的划分2.子问题的重叠。

本题按照从下至上的探查方式，构造的一个逻辑表是求解的关键

用一案例重点解读：

n=3 w=5

w={2,3,4}v={3,5,7}

注意事项:

参考代码:

n\v    1    2    3    4    5    

1    0    3    3    6    6    

2    0    3    5    6    8    

3    0    3    5    7    8   

全背包：

import java.util.*;
import java.math.*;

//背包问题之全背包
public class 背包问题 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int v = 0;// 价值
		int w = sc.nextInt();// 最大重量
		int n = sc.nextInt();// 物品总量
		int jiazhi[] = new int[n + 1];
		int zhongliang[] = new int[n + 1];
		int out[] = new int[n + 1];
		int q = 1;
		while (q <= n) {
			jiazhi[q] = sc.nextInt();
			zhongliang[q] = sc.nextInt();
			q++;
		}
		int arr[][] = new int[n + 1][w + 1];
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j < arr[i].length; j++) {
				if (i == 1) {
					arr[i][j] = (j / zhongliang[i]) * jiazhi[i];
				} else {
					if (j >= zhongliang[i]) {
						int one = arr[i - 1][j];
						int two = arr[i][j - zhongliang[i]] + jiazhi[i];
						arr[i][j] = one > two ? one : two;
					} else {
						arr[i][j] = arr[i - 1][j];
					}
				}
			}
		}
		v = arr[n][w];
		System.out.print(v);
	}
}

0-1背包：

n\v    1    2    3    4    5    

1    0    3    3    3    3    

2    0    3    5    5    5    

3    0    3    5    7    8    

import java.util.*;

public class 背包0_1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();// 物品总量
		int m = sc.nextInt();// 重量至高值
		int arr[][] = new int[n + 1][m + 1];
		int w[] = new int[n + 1];
		int v[] = new int[n + 1];
		int q = 1;
		while (q <= n) {
			w[q] = sc.nextInt();
			v[q] = sc.nextInt();
			q++;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j < arr[i].length; j++) {
				if (i == 1) {
					arr[i][j] = (j >= w[i]) ? v[i] : 0;
				} else {
					if (j >= w[i]) {
						int one = arr[i - 1][j];
						int two = arr[i-1][j - w[i]] + v[i];
						arr[i][j] = one > two ? one : two;
					} else {
						arr[i][j] = arr[i - 1][j];
					}
				}
			}
		}
		int vl = arr[n][m];
		System.out.print(vl);

	}
}