第一行输入两个整数
代表预算、查询到的物品总数。
此后
行,第
行输入三个整数
代表第
件物品的价格、重要度、主件编号。特别地,
代表该物品为主件,否则表示该附件从属于主件
。编号即输入顺序,从
开始。
特别地,保证全部物品的价格
均为
的倍数;且每个主件的附件数不超过
个。
在一行上输出一个整数,代表王强可获得的最大满意度。
50 5 20 3 5 20 3 5 10 3 0 10 2 0 10 1 0
130
在这个样例中,第三、四、五件物品为主件,第一、二件物品为第五件物品的附件。这就意味着,如果购买了第一件物品或第二件物品,则必须购买第五件物品;但是特别地,如果同时购买了第一件物品和第二件物品,则只需要购买一次第五件物品。
我们可以证明,购买一、二、五件商品,获得的满意度最大,为
。
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
2200
本题已于下方时间节点更新,请注意题解时效性:
1. 2025-05-15 更新题面,新增几组hack数据(暂未进行重测)。
2. 2024-12-13 更新题面。
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 总钱数 int n = scanner.nextInt(); // 购买物品个数 int m = scanner.nextInt(); // 分组,goods[i] Good[] goodList = new Good[m + 1]; //所有商品赋值 for (int i = 1; i <= m; i++) { int v = scanner.nextInt(); int w = scanner.nextInt(); int q = scanner.nextInt(); goodList[i] = new Good(v, w, q); //是否为主件 goodList[i].isMain = q == 0; } //遍历附件商品,赋给主件Good for (Good good1 : goodList) { if (good1 == null) { continue; } if (good1.isMain) {continue;} if (goodList[good1.q].subGood1 == null) { goodList[good1.q].subGood1 = good1; } else { goodList[good1.q].subGood2 = good1; } } //初始化动态规划数组 用以保存每个总价能得到的最大重要度 int[] dp = new int[n+1]; //再次遍历开始计算 for (Good good : goodList) { if (good == null) { continue; } //附件直接跳过 if (!good.isMain) {continue;} //考虑所有组合可能性,分为四类:只要主件 主件+附件1 主件+附件2 主件+附件1+附件2 int v = good.v; int ***bsp;= good.v * good.p; int[][] cases = new int[4][2]; //只要主件 cases[0] = new int[]{v,***bsp; //主件+附件1 if (good.subGood1 != null) { cases[1] = new int[]{v+good.subGood1.v,***bsp;+ (good.subGood1.v * good.subGood1.p)}; } if (good.subGood2 != null) { //主件+附件2 cases[2] = new int[]{v+good.subGood2.v,***bsp;+ (good.subGood2.v * good.subGood2.p)}; //主件+附件1+附件2 cases[3] = new int[]{v+good.subGood1.v+good.subGood2.v,***bsp;+ (good.subGood1.v * good.subGood1.p) + (good.subGood2.v * good.subGood2.p)}; } //开始动态数组更新 for (int j = n; j >= 0; j--) { for (int[] item : cases) { int cost = item[0]; int value = item[1]; if (cost > 0 && j >= cost) { dp[j] = Math.max(dp[j], dp[j - cost] + value); } } } } System.out.println(dp[n]); } } class Good { int v; //价格 int p; //重要度 int q; //主件编号 boolean isMain; Good subGood1; Good subGood2; public Good(int v, int p, int q) { this.v = v; this.p = p; this.q = q; } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int budget=in.nextInt(); int n=in.nextInt(); if(n<=0||budget<=0){ System.out.println(0); } good[] g=new good[n+1]; for(int i=1;i<=n;i++){ int v=in.nextInt(); int w=in.nextInt(); int q=in.nextInt(); if(g[i]!=null){ //如果g[i] 对象已创建,则只需赋值,否则要实例化 g[i].setvwq(v,w,q); }else{ g[i]=new good(v,w,q); } if(g[i].q>0){ //附件的主件对象未实例化时,先实例化 if(g[q]==null){ g[q]=new good(0,0,0); } g[q].setGood(g[i]); } } int dp[][]=new int[n+1][budget/10 +1]; for(int i=1;i<=n;i++){ int v=0,v1=0,v2=0,v3=0,sa=0,sa1=0,sa2=0,sa3=0; //只有主件(下一个循环语句中过滤掉附件) v=g[i].v; sa=g[i].v*g[i].w; //主件+附件1 if(g[i].good1!=null){ v1=v+g[i].good1.v; sa1=sa+g[i].good1.v*g[i].good1.w; } if(g[i].good2!=null){ //主件+附件2 v2=v+g[i].good2.v; sa2=sa+g[i].good2.v*g[i].good2.w; //主件+附件1+附件2 v3=v+g[i].good1.v+g[i].good2.v; sa3=sa+g[i].good1.v*g[i].good1.w+g[i].good2.v*g[i].good2.w; } for(int j=1;j<=budget/10;j++){ if(g[i].q>0){ //附件跳过 dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=dp[i-1][j]; if(j>=v/10&&v!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v/10]+sa); if(j>=v1/10&&v1!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v1/10]+sa1); if(j>=v2/10&&v2!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v2/10]+sa2); if(j>=v3/10&&v3!=0) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v3/10]+sa3); } } } System.out.println(dp[n][budget/10]); } public static class good{ int v; int w; int q; good good1; good good2; public good(int v,int w,int q){ this.v=v; this.w=w; this.q=q; } public void setvwq(int v,int w,int q){ this.v=v; this.w=w; this.q=q; } public void setGood(good goodChild){ if(this.good1==null){ this.good1=goodChild; }else if(this.good2==null){ this.good2=goodChild; } } } }
import java.util.LinkedList; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static class Product{ public int v; //价格 public int w; //重要程度 public int q; //主件编号 public Product(int a,int b,int c){ v=a;w=b;q=c; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int budget = scanner.nextInt(); //预算 int num = scanner.nextInt(); //商品数目 LinkedList<Product>[] list = new LinkedList[num]; //附件列表 for (int i = 0; i < num; i++) { list[i] = new LinkedList<>(); } Product[] products = new Product[num]; int[] dp = new int[budget+1]; //dp[i]代表的是i的预算去购买最大的满意度 for (int i = 0; i < num; i++) { int v = scanner.nextInt(); int w = scanner.nextInt(); int q = scanner.nextInt(); products[i] = new Product(v,w,q); if(q!=0){ list[q-1].add(products[i]); } } //当前可购买的列表只有0-i个商品 for(int i=0;i<num;i++){ //一件一件增加商品类别 //只考虑主件,附件是主件自带的 if(products[i].q>0) continue; for (int j = budget; j >=0 ; j-- ) { //从后往前,可以防止重复购买i件商品 if(j>=products[i].v) //当前的钱可以购买第j件产品 { // 选择购买当前第i件产品和不购买的满意度取max dp[j] = Math.max(dp[j],dp[j-products[i].v]+products[i].v*products[i].w); } //主件+附件 if(list[i].size()>0&&j>=products[i].v+list[i].getFirst().v){ dp[j] = Math.max(dp[j], dp[j-products[i].v-list[i].getFirst().v] + products[i].v*products[i].w + list[i].getFirst().v*list[i].getFirst().w); } if(list[i].size()>1&&j>=products[i].v+list[i].get(1).v){ //有两件附件 dp[j] = Math.max(dp[j],dp[j-products[i].v-list[i].get(1).v]+products[i].v*products[i].w+list[i].get(1).v*list[i].get(1).w); } if(list[i].size()>1&&j>=products[i].v+list[i].getFirst().v+list[i].get(1).v){ dp[j] = Math.max(dp[j],dp[j-products[i].v-list[i].getFirst().v-list[i].get(1).v]+products[i].v*products[i].w+list[i].get(1).v*list[i].get(1).w+list[i].getFirst().v*list[i].getFirst().w); } if(i==num-1) break; //最后一件产品不需要计算前面的数值 } } System.out.println(dp[budget]); } }
package org.example; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Shopping { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int yuSuan = in.nextInt(); int goodsNum = in.nextInt(); int[][] goodsArr = new int[goodsNum][3]; for (int i = 0; i < goodsNum; i++) { goodsArr[i][0] = in.nextInt(); goodsArr[i][1] = in.nextInt(); goodsArr[i][2] = in.nextInt(); } //为每个主件维护一个链表,代表其不同的价值选项 ArrayList<HashMap<Integer, Integer>> mainGoodsMapList = new ArrayList<HashMap<Integer, Integer>>(); for (int i = 0; i < goodsArr.length; i++) { if (goodsArr[i][2] == 0) { HashMap<Integer, Integer> valueMap = new HashMap<>(); valueMap.put(goodsArr[i][0], goodsArr[i][0] * goodsArr[i][1]); int maxValue = goodsArr[i][0] ; int maxSatisfaction = goodsArr[i][0] * goodsArr[i][1]; int fujianNum = 0; for (int j = 0; j < goodsArr.length; j++) { if (goodsArr[j][2] - 1 == i) { fujianNum++; maxValue += goodsArr[j][0]; maxSatisfaction += goodsArr[j][0] * goodsArr[j][1]; valueMap.put(goodsArr[i][0] + goodsArr[j][0], goodsArr[i][0] * goodsArr[i][1] + goodsArr[j][0] * goodsArr[j][1]); if (fujianNum == 2) { valueMap.put(maxValue, maxSatisfaction); } } } mainGoodsMapList.add(valueMap) ; } } int result = getMaxSatisfaction(mainGoodsMapList.size() - 1, mainGoodsMapList, yuSuan); System.out.println(result); } public static int getMaxSatisfaction(int newMainGoodsIndex, ArrayList<HashMap<Integer, Integer>> mainGoodsMapList , int yuSuan){ HashMap<Integer, Integer> newMainGoodsMap = mainGoodsMapList.get(newMainGoodsIndex); if(newMainGoodsIndex == 0){ if(yuSuan <= 0){ return 0; } int result = 0; int temp = 0; for(int item:newMainGoodsMap.keySet()){ if(item <= yuSuan && newMainGoodsMap.get(item) > temp){ result = newMainGoodsMap.get(item); } } return result; } else { int lastMaxSatisfaction = getMaxSatisfaction(newMainGoodsIndex-1, mainGoodsMapList, yuSuan); int currentMaxSatisfaction = lastMaxSatisfaction; for(int item:newMainGoodsMap.keySet()){ if(item <= yuSuan){ currentMaxSatisfaction = Math.max(currentMaxSatisfaction, newMainGoodsMap.get(item) + getMaxSatisfaction(newMainGoodsIndex-1, mainGoodsMapList, yuSuan-item) ); } } return currentMaxSatisfaction; } } }
import java.util.ArrayList; import java.util.Scanner; /** * Description: * Author: fy * Date: 2024/11/14 7:21 */ public class Main { static class Products { int price; int important; int index; public Products(int price, int important, int index) { this.price = price; this.important = important; this.index = index; } @Override public String toString() { return "价格:" + price + " 重要度:" + important + " 索引:" + index; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.nextLine(); String[] split = s.split(" "); int amount = Integer.parseInt(split[0]); int productCount = Integer.parseInt(split[1]); ArrayList<Products> mainList = new ArrayList<>(); ArrayList<ArrayList<Products>> attachList = new ArrayList<>(); for (int i = 0; i < productCount; i++) { attachList.add(new ArrayList<>()); } int record = 0; for (int i = 0; i < productCount; i++) { String proStr = in.nextLine(); String[] proSplit = proStr.split(" "); int price = Integer.parseInt(proSplit[0]); int important = Integer.parseInt(proSplit[1]); int mainProductIndex = Integer.parseInt(proSplit[2]); int index = record; if (mainProductIndex == 0) { //存主件 Products products = new Products(price, important, index); mainList.add(products); } else { //存附件 if (attachList.get(mainProductIndex - 1) == null) { attachList.set(mainProductIndex - 1, new ArrayList<>()); } Products products = new Products(price, important, index); attachList.get(mainProductIndex - 1).add(products); } record++; } int[] dp = new int[amount + 1]; dp[0] = 0; for (int i = 0; i < mainList.size(); i++) { Products products = mainList.get(i); int price = products.price; int important = products.important; int index = products.index; for (int j = amount; j > 0; j--) { //如果为空只考虑加或不加主件 if (attachList.get(index).isEmpty()) { if (j >= price) { dp[j] = Math.max(dp[j], dp[j - price] + important * price); } } else { //如果有附件 先看看存不存主件 if (j >= price) { dp[j] = Math.max(dp[j], dp[j - price] + important * price); } //在分别考虑 主件+附件1 和 主件+附件2 要不要为dp[j构成满意度 for (int k = 0; k < attachList.get(index).size(); k++) { Products attachProducts = attachList.get(index).get(k); int attachPrice = attachProducts.price; int attachImportant = attachProducts.important; if (j >= price + attachPrice) { dp[j] = Math.max(dp[j], dp[j - price - attachPrice] + important * price + attachImportant * attachPrice); } } //如果有两个附件 还要考虑主件+两个附件 要不要为dp[j]构成满意度 if (attachList.get(index).size() > 1) { Products attachProducts1 = attachList.get(index).get(0); int attachPrice1 = attachProducts1.price; int attachImportant1 = attachProducts1.important; Products attachProducts2 = attachList.get(index).get(1); int attachPrice2 = attachProducts2.price; int attachImportant2 = attachProducts2.important; int sumPrice = price + attachPrice1 + attachPrice2; int sumImportant = important * price + attachImportant1 * attachPrice1 + attachImportant2 * attachPrice2; if (j >= sumPrice) { dp[j] = Math.max(dp[j], dp[j - sumPrice] + sumImportant); } } } } } System.out.println(dp[amount]); } }
这是一个典型的0-1 背包问题的变种,其中存在主件和附件的约束关系。我们需要使用动态规划来解决这个问题。
主件和附件的关系:
目标:
思路:
package com.shisui.medium; import java.util.*; public class shopping_list { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 总钱数 int m = sc.nextInt(); // 物品个数 int[] dp = new int[N + 1]; // dp数组,dp[j]表示总价不超过j时的最大满意度 // 物品信息 Item[] items = new Item[m + 1]; List<Item>[] attachments = new List[m + 1]; // 初始化 for (int i = 0; i <= m; i++) { attachments[i] = new ArrayList<>(); } // 读取物品数据 for (int i = 1; i <= m; i++) { int v = sc.nextInt(); int p = sc.nextInt(); int q = sc.nextInt(); items[i] = new Item(v, p, q); if (q > 0) { attachments[q].add(items[i]); // 把附件添加到对应的主件附件列表中 } } // 动态规划求解 for (int i = 1; i <= m; i++) { if (items[i].q > 0) continue; // 处理附件时跳过 for (int j = N; j >= 0; j--) { // 从总钱数开始倒序遍历 // 主件选项 if (j >= items[i].v) { dp[j] = Math.max(dp[j], dp[j - items[i].v] + items[i].v * items[i].p); } // 主件+附件1选项 if (attachments[i].size() >= 1 && j >= items[i].v + attachments[i].get(0).v) { dp[j] = Math.max(dp[j], dp[j - items[i].v - attachments[i].get(0).v] + items[i].v * items[i].p + attachments[i].get(0).v * attachments[i].get(0).p); } // 主件+附件2选项 if (attachments[i].size() == 2 && j >= items[i].v + attachments[i].get(1).v) { dp[j] = Math.max(dp[j], dp[j - items[i].v - attachments[i].get(1).v] + items[i].v * items[i].p + attachments[i].get(1).v * attachments[i].get(1).p); } // 主件+附件1+附件2选项 if (attachments[i].size() == 2 && j >= items[i].v + attachments[i].get(0).v + attachments[i].get(1).v) { dp[j] = Math.max(dp[j], dp[j - items[i].v - attachments[i].get(0).v - attachments[i].get(1).v] + items[i].v * items[i].p + attachments[i].get(0).v * attachments[i].get(0).p + attachments[i].get(1).v * attachments[i].get(1).p); } } } System.out.println(dp[N]); } // 定义一个Item类来存储物品信息 static class Item { int v; // 价格 int p; // 重要度 int q; // 0表示主件,其他表示附件所属主件的编号 public Item(int v, int p, int q) { this.v = v; this.p = p; this.q = q; } } }
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { // 物品类 private static class good{ public int v; // 物品价格 public int p; // 重要程度 public int q; // 是否是附件 public good a1 = null; public good a2 = null; public good(int v, int p, int q){ this.v = v; this.p = p; this.q = q; } public void setAppendGoods(good a){ if(this.a1 == null) this.a1 = a; else this.a2 = a; } public boolean isFollowed(){ if(this.a1 == null && this.a2 == null) return false; else return true; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); // 钱数 int n = in.nextInt(); // 购买物品数 List<good> input_good = new ArrayList<>(); // 存储输入值 List<good> input_follow_good = new ArrayList<>(); Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // 存储主件位置 int totalCount = 0; // 记录主件原始数组中位置 int mainCount = 0; // 记录主件在主件数组中位置 while(in.hasNext()){ int v = in.nextInt(); int p = in.nextInt(); int q = in.nextInt(); if(q != 0) input_follow_good.add(new good(v, p, q)); else{ input_good.add(new good(v, p ,q)); map.put(totalCount,mainCount); mainCount++; } totalCount++; } int index = 0; // 插入辅件 if(!input_follow_good.isEmpty()){ for(good g:input_follow_good){ index = map.get(g.q-1); input_good.get(index).setAppendGoods(g); } } int len = input_good.size(); int[][] dp = new int[m+1][len+1]; // 边界条件 - dp[0][j] = 0 | dp[i][0] = 0 // 辅件计算 - 0 选1 选2 两个都选 // 状态转换方程 (不带辅件)dp[i][j] = Max(dp[i][j-1], dp[i-input[j][0]][j-1] + input[j][0] * input[j][1]) (携带辅件)dp[i][j] = Max(dp[i][j-1], dp[i-input[j][0]][j-1] + input[j][0] * input[j][1], dp[i-input[j][0]-input[j1][0]][j-1] + input[j][0] * input[j][1] +input[j1][0] * input[j1][1], ***) for(int i=1; i<m+1; i++){ for(int j=1; j<len+1; j++){ good temp = input_good.get(j-1); dp[i][j] = dp[i][j-1]; if(i-temp.v >= 0){ dp[i][j] = Math.max(dp[i][j-1], dp[i-temp.v][j-1]+temp.v*temp.p); if(temp.isFollowed()){ if(temp.a1 != null && i-temp.v-temp.a1.v >= 0) // 带附件1 dp[i][j] = Math.max(dp[i][j],dp[i-temp.v-temp.a1.v][j-1]+temp.v*temp.p+temp.a1.v*temp.a1.p); if(temp.a2 != null && i-temp.v-temp.a2.v >= 0) // 带附件2 dp[i][j] = Math.max(dp[i][j],dp[i-temp.v-temp.a2.v][j-1]+temp.v*temp.p+temp.a2.v*temp.a2.p); if(temp.a1 != null && temp.a2 != null && i-temp.v-temp.a1.v-temp.a2.v >= 0) // 带附件1和2 dp[i][j] = Math.max(dp[i][j],dp[i-temp.v-temp.a1.v-temp.a2.v][j-1]+temp.v*temp.p+temp.a1.v*temp.a1.p+temp.a2.v*temp.a2.p); } } } } System.out.println(dp[m][len]); } }
个人也是第一次接触算法这个领域,本身只是个搬砖的,如果解法有不好的地方,欢迎各位指出。
import java.util.ArrayList; import java.util.List; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int limitMoney = in.nextInt(); int n = in.nextInt(); List<Goods> goodsList = new ArrayList<Goods>(); for (int i = 0; i < n; i++) { int price = in.nextInt(); int value = in.nextInt() * price; int type = in.nextInt(); Goods goods = new Goods(i + 1, price, value, type); goodsList.add(goods); } ShoppingPlan shoppingPlan = calculateMaxValue(goodsList, limitMoney); System.out.println(shoppingPlan.getTotalValue()); } } public static ShoppingPlan calculateMaxValue(List<Goods> goodsList, int limitMoney) { // 最大公约数 int gcd = getArrayGcd(goodsList); int n = goodsList.size(); int m = limitMoney / gcd; ShoppingPlan[][] dp = new ShoppingPlan[n + 1][m + 1]; // 初始化边界 dp[0][0] = new ShoppingPlan(); for (int i = 1; i <= n; i++) { dp[i][0] = dp[0][0]; } for (int j = 1; j <= m; j++) { dp[0][j] = dp[0][0]; } // 计算动态规划矩阵 for (int i = 1; i <= n; i++) { Goods goods = goodsList.get(i - 1); for (int j = 1; j <= m; j++) { // 构建新的购物方案 ShoppingPlan plan = new ShoppingPlan(); // 基础方案的索引值 int planIndex = j - goods.getPrice() / gcd; // 是否附件 if (goods.isAttachment()) { // 索引之需大于等于0,购买的钱才是足够的 if (planIndex >= 0) { // 获取主件 Goods mainGoods = goodsList.get(goods.getType() - 1); // 判断选取的基础方案是否有主件,决定是否添加主件 boolean hasMainGoods = dp[i - 1][planIndex].hasMainGoods(goods); if (!hasMainGoods) { // 如果选取的基础方案没有购买主件,则需要腾出购买主件的钱,需要将基础方案再往前推 planIndex -= mainGoods.getPrice() / gcd; } // 腾出钱之后,看看够不够买,如果不够,那就不使用基础方案了,使用新方案从头开始 if (planIndex >= 0) { // 前如果够那就复制一份基础方案 plan = dp[i - 1][planIndex].createSnapshot(); } // 然后再加上买主件 if (!hasMainGoods) { plan.addGoods(mainGoods); } } } else { // 主件处理 if (planIndex >= 0) { // 只需要判断钱够不够就行了,方案的索引大于0,就是够钱出方案,复制一份基础方案继续购买 plan = dp[i - 1][planIndex].createSnapshot(); } } // 无论主件附件都是需要加进方案判断的 plan.addGoods(goods); // 看看新生成的计划有没有超过目前的钱 if (plan.getTotalPrice() <= j * gcd) { // 如果钱够,则比较上个商品使用这么多钱的方案,然后再判断哪个方案的满意度高,择优获取 dp[i][j] = ShoppingPlan.max(dp[i - 1][j], plan); continue; } // 不够钱买新方案的,那就用上个商品在这个钱的方案 dp[i][j] = dp[i - 1][j]; } } // 将最终的方案返回 return dp[n][m]; } /** * 商品 */ public static class Goods { // 商品编号 private int id; // 商品单价 private int price; // 商品价值(满意度) private int value; // 商品类型(主件为0,附件大于0) private int type; public Goods(int id, int price, int value, int type) { this.id = id; this.price = price; this.value = value; this.type = type; } public int getId() { return this.id; } public int getPrice() { return this.price; } public int getValue() { return this.value; } public int getType() { return this.type; } /** * 商品是否附件 * @return true/false */ public boolean isAttachment() { return this.type > 0; } } /** * 购物方案 */ public static class ShoppingPlan { // 商品列表 private List<Goods> goodsList; // 总金额 private int totalPrice; // 总价值(总满意度) private int totalValue; /** * 构造函数,需要输入方案编号 */ public ShoppingPlan() { this.goodsList = new ArrayList<Goods>(); this.totalPrice = 0; this.totalValue = 0; } private ShoppingPlan(List<Goods> goodsList, int totalPrice, int totalValue) { this.goodsList = goodsList; this.totalPrice = totalPrice; this.totalValue = totalValue; } /** * 添加商品,同时会累计总金额和总价值 * @param goods 商品 */ public void addGoods(Goods goods) { this.goodsList.add(goods); this.totalPrice += goods.getPrice(); this.totalValue += goods.getValue(); } public int getTotalPrice() { return this.totalPrice; } public int getTotalValue() { return this.totalValue; } /** * 判断方案中是否存在当前附件的主件 * @param attachment 附件商品 * @return true/false */ public boolean hasMainGoods(Goods attachment) { for (Goods mainGoods : this.goodsList) { if (mainGoods.getId() == attachment.getType()) { return true; } } return false; } /** * 复制购物方案(不会影响到原购物方案信息) * @return 购物方案副本 */ public ShoppingPlan createSnapshot() { List<Goods> goodsList = new ArrayList<Goods>(this.goodsList.size()); goodsList.addAll(this.goodsList); return new ShoppingPlan(goodsList, this.totalPrice, this.totalValue); } /** * 获取满意度高的方案 * @param a 购物方案a * @param b 购物方案b * @return 满意度高的方案 */ public static ShoppingPlan max(ShoppingPlan a, ShoppingPlan b) { if (a.getTotalValue() >= b.getTotalValue()) { return a; } return b; } } /** * 用更相减损法计算公约数 * @param a 数a * @param b 数b * @return 最大公约数 */ public static int gcd(int a, int b) { if (a < b) { int tmp = a; a = b; b = tmp; } return (a % b == 0) ? b : gcd(a - b, b); } /** * 计算数组里的所有数的最大公约数 * @param goodsList 源数据数组 * @return 数组里的所有数的最大公约数 */ public static int getArrayGcd(List<Goods> goodsList) { int gcd = goodsList.get(0).getPrice(); for (int i = 1; i < goodsList.size(); i++) { gcd = gcd(gcd, goodsList.get(i).getPrice()); } return gcd; } }
这个题是背包问题的变种,基础解法是二维动态规划。不过,由于加了主件和附件的限制,需要判断的东西一下子多了很多。本人脑子不够用,就将有可能用到的西信息封装起来了,一共是两个类:ShoppingPlan(购物方案)和Goods(商品)
商品的基础属性是不会变的,通过调整购物方案里的商品列表做动态规划达到最优。
说一下动态规划二位数组的生成思路。
如果是一维的动态规划,我们可以知道它的思路是递推,也就是前面方案作为基础方案不断积累,数组的最后一个元素dp[n]就是最后的结果。一维的题,一般每一步都是一定会发生,且有规律的,只是发生的时间有交错。
沿着一维动态规划的思路拓展到二维,那就是经典的背包问题,按每件物品的选取累计,但是跟一维不同的是,物品可选可不选,这样就衍生出了分支,所以需要使用二维来记录分支。然后通过前两个物品选出来的方案作为基础,用上一个物品加入基础方案,和当前物品加入基础方案,这两个方案作比较,择优设置到当前的方案中。
背包数组的纵向是物品,横向记录了选取和不选取的值
回到商品选取,商品选取的话大致思路是按照背包问题构筑的,由于加入了主件附件联动,我们需要考虑以下问题:
1.当前的商品是否附件,如果是就需要跟主件一起计算金额
2.基础方案是否包含了主件,如果包含的话,就不能将主件再加到购物方案里面了,只能加附件
3.如果基础方案没有主件,那么我需要腾出钱去买主件,如果剩下的钱不够了,我还需要换一个基础方案,再加上主件附件,然后去比较
梳理之后,发现问题可以按以下思路解决:
1.判断商品是否附件,如果是主件,那么直接看钱够不够,然后跟上个商品在这个钱的旧方案比较就好
2.如果是附件,那么一直加钱,直到满足有一个基础方案+附件的新方案出来,如果没有,就用同价格上个商品的方案
3.判断基础方案中是否已存在主件,如果不存在主件的话,加上主件的价格,一直加钱,直到有一个基础方案+主件+附件的新方案出来,没有的话,用铜价格上个商品的方案
最后发现,同时满足钱够且满意度高才会替换方案,所以最后二维数组最后一个元素就是最优的购物方案。
由于按1块钱去构造数组和循环,会产生大量的同样的方案,且处理时间非常长,所以采用了求取商品数组的最大公约数简化数组的构成和缩短计算时间。
import java.util.Objects; import java.util.Scanner; public class Interview { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String input = scanner.nextLine(); String[] priceAndNum = input.split(" "); int price = Integer.parseInt(priceAndNum[0]); int num = Integer.parseInt(priceAndNum[1]); Goods[] goodsList = new Goods[num]; for (int i = 0; i < num; i++) { String goodsInfo = scanner.nextLine(); String[] goodsArray = goodsInfo.split(" "); Goods goods = new Goods(); goods.setPrice(Integer.parseInt(goodsArray[0])); goods.setSatisfy(Integer.parseInt(goodsArray[1])); goods.setAttachId(Integer.parseInt(goodsArray[2])); goodsList[i] = goods; } for (int i = 0; i < num; i++) { Goods goods = goodsList[i]; if (goods.attachId > 0) { Goods main = goodsList[goods.attachId - 1]; if (Objects.isNull(main.getFirstAttach())) { main.setFirstAttach(i); } else { main.setSecondAttach(i); } } } int [][] dp = new int[num + 1][price + 1]; //遍历所有商品 for (int i = 1; i <= num; i++) { Goods goods = goodsList[i - 1]; //4中情况 1:主件 2:主件+附件1 3:主件+附件2 4:主件+附件1+附件2 int mainSatisfy = goods.price * goods.satisfy; boolean ifAttach1 = Objects.nonNull(goods.firstAttach); boolean ifAttach2 = Objects.nonNull(goods.secondAttach); int attach1Price = ifAttach1 ? goodsList[goods.firstAttach].price : 0; int attach2Price = ifAttach2 ? goodsList[goods.secondAttach].price : 0; int attach1Satisfy = ifAttach1 ? mainSatisfy + goodsList[goods.firstAttach].satisfy * goodsList[goods.firstAttach].price : 0; int attach2Satisfy = ifAttach2 ? mainSatisfy + goodsList[goods.secondAttach].satisfy * goodsList[goods.secondAttach].price : 0; int attach1And2 = ifAttach2 && ifAttach1 ? attach1Satisfy + attach2Satisfy - mainSatisfy : 0; //遍历预算,动态找出满足价格范围内的最大满意度 for (int j = 1; j <= price; j++) { dp[i][j] = dp[i - 1][j]; if (goods.attachId > 0) { //如果是附件,那么不放dp,dp的值为放进一件、两件、三件...商品时的最大满意度 continue; } if (j - goods.price >= 0) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price] + mainSatisfy); } if (ifAttach1 && (j - (goods.price + attach1Price) >= 0)) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price - attach1Price] + attach1Satisfy); } if (ifAttach2 && (j - (goods.price + attach2Price) >= 0)) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price - attach2Price] + attach2Satisfy); } if (ifAttach1 && ifAttach2 && (j - (goods.price + attach1Price + attach2Price) >= 0)) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.price - attach1Price - attach2Price] + attach1And2); } } } System.out.println(dp[num][price]); } static class Goods { private Integer price; private Integer satisfy; private Integer attachId; private Integer firstAttach; private Integer secondAttach; public Integer getPrice() { return price; } public void setPrice(Integer price) { this.price = price; } public Integer getSatisfy() { return satisfy; } public void setSatisfy(Integer satisfy) { this.satisfy = satisfy; } public Integer getAttachId() { return attachId; } public void setAttachId(Integer attachId) { this.attachId = attachId; } public Integer getFirstAttach() { return firstAttach; } public void setFirstAttach(Integer firstAttach) { this.firstAttach = firstAttach; } public Integer getSecondAttach() { return secondAttach; } public void setSecondAttach(Integer secondAttach) { this.secondAttach = secondAttach; } } }
import java.util.*;
public class Main {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int m = in.nextInt(); int[] v = new int[m + 1]; //价格 int[] p = new int[m + 1]; //重要度 int[] q = new int[m + 1]; //所属主件编号 for (int i = 1 ; i 1 ; i++) { v[i] = in.nextInt(); p[i] = in.nextInt(); q[i] = in.nextInt(); } System.out.println(getMaxSat(v, p, q, N, m)); } //获取最大满意值方法 public static int getMaxSat(int[] v, int[] p, int[] q, int N, int m) { Good[][] good = new Good[m + 1][3]; //g[i][j]表示i号物品的第j个附件(最多2个),i=0表示i号商品是主件,g[i][0]为空表示i号商品为附件 int max = 0; int[] sat = new int [N + 1]; //sat[i]表示花费i元时的满意度 //跟据条件初始化good对象数组 for (int i = 1 ; i <= m ; i++) { Good gt = new Good(v[i], v[i] * p[i]); if (q[i] == 0) { good[i][0] = gt; } else { //是附件时判断是否存在另一个附件 if (good[q[i]][1] == null) good[q[i]][1] = gt; else good[q[i]][2] = gt; } } for (int i = 1; i <= m; i++) { for (int j = N; j >= 0; j--) { Good gt0 = good[i][0]; Good gt1 = good[i][1]; Good gt2 = good[i][2]; // i号商品不是主件时跳过循环 if (gt0 == null) break; // 第i号物品为主件时列出四种情况:主,主+附1,主+附2,主+附1+附2,并记录四种情况下的最大的满意度 else { //该主件没有附件 if (gt1 == null && gt2 == null) { if (gt0.v <= j) { //和原来的sat[j]比较,取最大满意度并记录 sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]); } } //该主件有1个附件,若剩余金额允许购买主件和附件,比较主和主+附1的最大满意度 if (gt1 != null) { if (gt0.v <= j) { sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]); } if (gt0.v + gt1.v <= j) { sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + sat[j - gt0.v - gt1.v]); } } //该主件有2个附件,若剩余金额允许购买主件和附件,比较主,主+附1,主+附2,主+附1+附2的最大满意度 if (gt2 != null) { if (gt0.v <= j) { sat[j] = Math.max(sat[j], gt0.vp + sat[j - gt0.v]); } if (gt0.v + gt1.v <= j) { sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + sat[j - gt0.v - gt1.v]); } if (gt0.v + gt2.v <= j) { sat[j] = Math.max(sat[j], gt0.vp + gt2.vp + sat[j - gt0.v - gt2.v]); } if (gt0.v + gt1.v + gt2.v <= j) { sat[j] = Math.max(sat[j], gt0.vp + gt1.vp + gt2.vp + sat[j - gt0.v - gt1.v - gt2.v]); } } } } } return sat[N]; }
}
//定义商品类
class Good {
int v;//价格 int vp;//满意度 public Good(int v, int vp) { this.v = v; this.vp = vp; }
}
import java.util.ArrayList; import java.util.List; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.StringTokenizer; import java.util.concurrent.ConcurrentHashMap; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer line = new StringTokenizer(br.readLine()); int money = Integer.parseInt(line.nextToken()); int num = Integer.parseInt(line.nextToken()); Good[] goods = new Good[num]; int i = 0; while (i < num) { line = new StringTokenizer(br.readLine()); int v = Integer.valueOf(line.nextToken()); int p = Integer.valueOf(line.nextToken()); int q = Integer.valueOf(line.nextToken()); if (goods[i] == null) { goods[i] = new Good(v, p, q); } else { goods[i].v = v; goods[i].p = p; goods[i].q = q; } if (q > 0) { // 附件 if (goods[q - 1] == null) { // 主件还未创建 goods[q - 1] = new Good(0, 0, 0); } if (goods[q - 1].g1 < 0) { goods[q - 1].g1 = i; } else { goods[q - 1].g2 = i; } } i++; } System.out.println(shopping(goods, money)); } public static int shopping(Good[] goods, int money) { int dp[] = new int[money + 1]; for (int i = 0; i < goods.length; i++) { Good g = goods[i]; for (int j = money; j >= g.v && g.q == 0; j--) { // 只买主件 dp[j] = Math.max(dp[j - g.v] + g.p * g.v, dp[j]); // 主 + 附1 if (g.g1 >= 0 && j >= (g.v + goods[g.g1].v)) { Good g1 = goods[g.g1]; dp[j] = Math.max(dp[j - g.v - g1.v] + g.p * g.v + g1.v * g1.p, dp[j]); } // 主 + 附2 if (g.g2 >= 0 && j >= (g.v + goods[g.g2].v)) { Good g2 = goods[g.g2]; dp[j] = Math.max(dp[j - g.v - g2.v] + g.p * g.v + g2.v * g2.p, dp[j]); } // 主 + 附1 + 附2 if (g.g1 >= 0 && g.g2 >= 0 && j >= (g.v + goods[g.g1].v + goods[g.g2].v)) { Good g1 = goods[g.g1]; Good g2 = goods[g.g2]; dp[j] = Math.max(dp[j - g.v - g1.v - g2.v] + g.p * g.v + g1.v * g1.p + g2.v * g2.p, dp[j]); } } } return dp[money]; } public static class Good { private int v; // 价格 private int p; // 重要性 private int q; // 主件id private int g1 = -1; // 附件1 private int g2 = -1; // 附件2 public Good(int v, int p, int q) { this.v = v; this.p = p; this.q = q; } } }