Dumas


私信TA

用户名:lvanan

访问量:5884

签 名:

不爱学历,只爱学力。

等  级
排  名 2815
经  验 2150
参赛次数 0
文章发表 13
年  龄 0
在职情况 学生
学  校 河南农业大学
专  业

  自我简介:

解题思路:
解决背包问题,首先要看通俗背包如何解决,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);

	}
}


 

0.0分

2 人评分

新上线《蓝桥杯辅导》课程,近五年的蓝桥杯省赛与国赛真题都有,从读题开始理解题意、梳理思路、实现代码再提交评测全过程,可有效提升获奖比例甚至进国赛!课程介绍、试听请猛击这里

  评论区

  • «
  • »