网站需要服务器,网络营销推广与策划总结,阿里云oss做网站,小学生信息科学做网站01背包
题目链接#xff1a;卡码网第46题
二维解题思路#xff1a;需要建立一个i行k列的dp数组#xff0c;i表示每个物品#xff0c;k代表容量#xff0c;初始化数组子一列为0#xff0c;第一行从背包开始能够放入起始为价值#xff0c;其他都为0。for双循环先背包后物…01背包
题目链接卡码网第46题
二维解题思路需要建立一个i行k列的dp数组i表示每个物品k代表容量初始化数组子一列为0第一行从背包开始能够放入起始为价值其他都为0。for双循环先背包后物品还是先物品后背包都可以。主要代码dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weight] value);
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int kind scanner.nextInt(); // 研究材料的种类数int size scanner.nextInt(); // 小明的行李空间int[] weights new int[kind]; // 每种材料的占用空间int[] values new int[kind]; // 每种材料的价值// 读取占用空间for (int i 0; i kind; i) {weights[i] scanner.nextInt();}// 读取价值for (int i 0; i kind; i) {values[i] scanner.nextInt();}// 定义dp数组int[][] dp new int[kind 1][size 1];// 动态规划求解背包问题for (int i 1; i kind; i) {int weight weights[i - 1];int value values[i - 1];for (int j 0; j size; j) {if (j weight) {dp[i][j] dp[i - 1][j]; // 当前物品无法放入} else {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weight] value); // 选择放或不放}}}// 输出结果System.out.println(dp[kind][size]); // 背包最大价值scanner.close();}
}一维解题思路需要建立一个k大小的的dp数组k代表容量初始化数组子一列为0背包倒序计算内部最大价值即从大容量向小容量计算因为从小容量向大容两计算的时候 dp[i - 1][j - weight] value可能重复计算当前物品已经放入过的情况。双层for循环先物品后背包倒序循环。主要代码dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weight] value); 416. 分割等和子集 题目链接力扣题目链接 思路背包大小就是整个数组的之和的一半如果是奇数不成立。然后想象成大小和价值一样容量就是数组之和的一半即可。
