陕西示范校建设专题网站,招工网站58同城,个人网站设计流程步骤,wordpress文章布局提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、01背包二、完全背包1.引入库 三.多重背包优化#xff1a; 四.分组背包总结 前言
提示#xff1a;这里可以添加本文要记录的大概内容#xff1a;
例如文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、01背包二、完全背包1.引入库 三.多重背包优化 四.分组背包总结 前言
提示这里可以添加本文要记录的大概内容
例如随着人工智能的不断发展机器学习这门技术也越来越重要很多人都开启了学习机器学习本文就介绍了机器学习的基础内容。 提示以下是本篇文章正文内容下面案例可供参考
一、01背包
import java.util.Scanner;
public class Main{public static void main(String[] args) throws Exception {// 读入数据的代码Scanner reader new Scanner(System.in);// 物品的数量为Nint N reader.nextInt();// 背包的容量为Vint V reader.nextInt();// 一个长度为N的数组第i个元素表示第i个物品的体积int[] v new int[N 1] ;// 一个长度为N的数组第i个元素表示第i个物品的价值int[] w new int[N 1] ;for (int i1 ; i N ; i){// 接下来有 N 行每行有两个整数:v[i],w[i]用空格隔开分别表示第i件物品的体积和价值v[i] reader.nextInt();w[i] reader.nextInt();}reader.close() ;// 正式工作的代码/*定义一个二阶矩阵dp[N1][V1],这里之所以要N1和V1是因为第0行表示只能选择第0个物品的时候即没有物品的时候第0列表示背包的体积为0的时候即不能装任何东西的时候dp[i][j]表示在 只能选择前i个物品背包容量为j的情况下背包中物品的最大价值对于dp[i][j]有两种情况1. 不选择当前的第i件物品/第i件物品比背包容量要大则dp[i][j] dp[i-1][j]2. 选择当前的第i件物品潜在要求第i件物品体积小于等于背包总容量则能装入的物品最大价值为当前物品的价值 加上 背包剩余容量在只能选前i-1件物品的情况下的最大价值dp[i][j] dp[i-1][j-v[i]] w[i]dp[i][j]在两种情况中选择比较大的情况作为当前的最优解即if(j v[i]):dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])else:dp[i][j] dp[i-1][j]*/int[][] dp new int[N1][V1];dp[0][0] 0;for(int i 1; i N; i){for(int j 0; j V; j){if(j v[i]){dp[i][j] Math.max(dp[i-1][j], dp[i-1][j-v[i]] w[i]);}else{dp[i][j] dp[i-1][j];}}}System.out.println(dp[N][V]);}
}
二、完全背包
1.引入库
import java.util.Scanner;
public class Main {static int N1010;static Scanner scnew Scanner(System.in);static int nsc.nextInt();static int msc.nextInt();static int v[]new int[N]; //体积static int w[]new int[N]; //价值static int f[][]new int[N][N];public static void main(String[] args) {for(int i1;in;i) {v[i]sc.nextInt();w[i]sc.nextInt();}for(int i1;in;i) { //针对当前的第i个物品for(int j0;jm;j) { //枚举所消耗的体积for(int k0;k*v[i]j;k) {f[i][j]Math.max(f[i][j], f[i-1][j-k*v[i]]w[i]*k);}}}System.out.println(f[n][m]);}}
三.多重背包
代码如下示例
/*
1. 状态定义 已经选了1...i种物品且背包体积 j 时的最大值 - 优化为f[j]
2. 状态计算 以最后一次选i划分为选还是不选根据遍历体积转化为选几次 即 f[j] MAX (f[j - k* v[i]] k*w[i] )
3. 边界f[~] 0
*/
import java.util.*;
public class Main{void run(){int n jin.nextInt();int m jin.nextInt();for (int i 1 ; i n ; i) {v[i] jin.nextInt();w[i] jin.nextInt();s[i] jin.nextInt();}int res dp(n, m);System.out.println(res);}int dp(int n, int m){int[] f new int[maxN];for (int i 1 ; i n ;i ){for (int j m ; j v[i] ; j--){for (int k 0 ; k s[i] k* v[i] j ;k){// 把最简单的完全背包改写下f[j] Math.max(f[j], f[j - k* v[i]] k* w[i]);}}}return f[m];}int maxN 1002;int[] v new int[maxN];int[] w new int[maxN];int[] s new int[maxN];Scanner jin new Scanner(System.in);public static void main(String[] args) {new Main().run();}
}
优化
#includeiostream
using namespace std;const int N 1010;int n, m;
int dp[N];int main(){cin n m;for(int i 1; i n; i ){int v, w;cin v w;for(int j v; j m; j ){dp[j] max(dp[j], dp[j - v] w);}}cout dp[m] endl;
}
四.分组背包
import java.io.*;
public class Main {static int N, V;static int[][] f;static int[] v new int[101];static int[] w new int[101];//因为每组中物品的体积和价值不知道所以直接取个最大值static BufferedReader reader new BufferedReader(new InputStreamReader(System.in));static BufferedWriter writer new BufferedWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException {String[] str reader.readLine().split( );N Integer.parseInt(str[0]);V Integer.parseInt(str[1]);f new int[N 1][V 1];for (int i 1; i N; i) {int s Integer.parseInt(reader.readLine());for (int k 1; k s; k) {String[] str1 reader.readLine().split( );int v1 Integer.parseInt(str1[0]);int w1 Integer.parseInt(str1[1]);v[k] v1;w[k] w1;}for (int j 0; j V; j) {for (int k 0; k s; k) {//从每组中的si件物品中选择使f[i][j]总价值最大的if (j v[k]) {f[i][j] Math.max(f[i][j], f[i - 1][j - v[k]] w[k]);}}}}writer.write(f[N][V] );writer.flush();writer.close();reader.close();}
}
总结
提示这里对文章进行总结 例如以上就是今天要讲的内容本文仅仅简单介绍了pandas的使用而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
