建设银行网站用户名,阿里邮箱企业版登录入口,wordpress 作者id,宜城网站定制1.01背包
题目描述 小明有一个容量为 V 的背包。
这天他去商场购物#xff0c;商场一共有N 件物品#xff0c;第 i 件物品的体积为 wi#xff0c;价值为 vi。
小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少#xff0c;请你帮他算算。
输入描述…1.01背包
题目描述 小明有一个容量为 V 的背包。
这天他去商场购物商场一共有N 件物品第 i 件物品的体积为 wi价值为 vi。
小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少请你帮他算算。
输入描述 输入第 11 行包含两个正整数 N,V表示商场物品的数量和小明的背包容量。
第 2∼N1 行包含 2 个正整数 w,v表示物品的体积和价值。
1≤N≤100 ,1≤V≤1000,≤wi,vi≤10000。
输出描述 输出一行整数表示小明所能获得的最大价值。
样例
输入
5 20
1 6
2 5
3 8
5 15
3 3 输出
37
代码示例
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);//在此输入您的代码...int n scan.nextInt();int m scan.nextInt();int[] w new int[m1];int[] v new int[n1];for(int i 1;in;i){v[i] scan.nextInt();w[i] scan.nextInt();}int[][] dp new int[n1][m1];for(int i 1;in;i){for(int j 1;jm;j){if(jv[i]){dp[i][j] Math.max(dp[i][j-v[i]]w[i],dp[i-1][j]);}else{dp[i][j] dp[i-1][j];}}}System.out.println(dp[n][m]);scan.close();}
}2.完全背包
问题描述
有 N 件物品和一个体积为 M 的背包。第 ii 个物品的体积为 vi价值为 wi。每件物品可以使用无限次。
请问可以通过什么样的方式选择物品使得物品总体积不超过 M 的情况下总价值最大输出这个最大价值即可。
输入格式
第一行输入两个正整数 N,M。(1≤N,M≤1000)(1≤N,M≤1000)
接下来 NN 行每行输入两个整数 vi,wi。(0≤vi,wi≤1000)(0≤vi,wi≤1000)
输出格式
输出一个整数表示符合题目要求的最大价值。
样例输入
4 5
1 2
2 4
3 4
4 5样例输出
10说明
你可以选择 1 个第一个物品和 2 个第二个物品。
代码示例
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in); int n sc.nextInt(); // 物品数量int m sc.nextInt(); // 背包容量int[] w new int[n]; // 物品体积数组int[] v new int[n]; // 物品价值数组// 输入每种物品的体积和价值for (int i 0; i n; i) {w[i] sc.nextInt();v[i] sc.nextInt();}// 创建一个一维数组dpdp[i]表示背包容量为i时的最大价值int[] dp new int[m 1];// 动态规划求解for (int i 0; i n; i) {for (int j w[i]; j m; j) {dp[j] Math.max(dp[j - w[i]] v[i], dp[j]);}}// 输出最大价值System.out.println(dp[m]);}
}
