)
零食奖励
2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型
华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解
题目描述
小朋友考试得第一名就可以得到零食奖励。现在价格A、B、C、D、E、…，元商品名A1、B1、C1、D1、E1、…，小朋友的喜爱度依次为A2、B2、C2、D2、E2、…。请返回选取x元零食可以达到的最大喜爱度。
输入描述
第一行输入为x和N，x为可使用的钱的总额，N为零食种类数。
0 ≤ x ≤ 1000
0 ≤ N ≤ 100
第二行开始为零食属性，每行有三个整型数值，分别代表零食的价格、数量和喜爱度。
零食价格(0,100)
零食个数[0,10000]
零食喜爱度[0,10000]
输出描述
最大喜爱度
用例1
输入
10 2 2 4 3 3 3 4输出
14说明
可选第1种零食最多 4 个，第2种最多 3 个。最佳选择为：选 2 个第2种（花费 6 元，喜爱度 8）和 2 个第1种（花费 4 元，喜爱度 6），总计花费 10 元，总喜爱度 14。输出 14。
用例2
输入
6 7 3 1 8 4 1 2 3 1 1 9 1 7 4 1 1 5 1 8 4 1 4输出
9说明
6元可以购买两个3元的零食，喜爱度综合为8+1=9
题解
思路：多重背包问题
多重背包问题的典型题，相比于普通背包问题，多加了数量的限制，如果数据量小于 10^2可以将多重背包转换为普通背包也没问题，但是本题大于这个数量级所以需要进行多重背包二进制优化来处理这个问题。- 二进制优化的逻辑如下: 本质上利用的原理是
十进制数 都可以由一个或多个2^x数表示。优化逻辑 例如count为10,使用普通背包会拆分为10个1{1,1,1,1,1,1,1,1,1,1}, 使用二进制拆分会被拆分为{1,2,4}只会拆分为3个注意这样拆分之后对应喜爱度和成本也会 * 拆分对应值，所以能减少将拆分复杂度从O(count) -> O(log count) - 明白2的定理之后，接下来就和普通背包处理一致，定义
dp[x + 1], dp[i]代表i的金额能获得最大喜爱度。然后循环遍历每个零食，然后使用二进制拆分优化，然后使用普通背包进行处理就可。对应状态方程为dp[j] = max(dp[j], dp[j - cost] + value) - 根据3的逻辑处理所有零食之后，输出的
dp[x]就是结果。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; int main() { int x, n; cin >> x >> n; // dp[i]代表i元能获得的最大喜爱度 vector<int> dp(x + 1, 0); for(int i = 0; i < n; i++) { int price,count,love; cin >> price >> count >> love; // 二进制优化多重背包 for (int k = 1; count > 0; k <<=1) { int cnt = min(k, count); int cost = cnt * price; int value = cnt * love; count -= cnt; for (int j = x; j >= cost; j--) { dp[j] = max(dp[j], dp[j- cost] + value); } } } cout << dp[x] << endl; return 0; }JAVA
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); // 总钱数 int n = sc.nextInt(); // 食物种类 int[] dp = new int[x + 1]; // dp[i]表示花i元能获得的最大喜爱度 for (int i = 0; i < n; i++) { int price = sc.nextInt(); int count = sc.nextInt(); int love = sc.nextInt(); // 二进制优化多重背包 for (int k = 1; count > 0; k <<= 1) { int cnt = Math.min(k, count); int cost = cnt * price; int value = cnt * love; count -= cnt; for (int j = x; j >= cost; j--) { dp[j] = Math.max(dp[j], dp[j - cost] + value); } } } System.out.println(dp[x]); } }Python
x,n=map(int,input().split())dp=[0]*(x+1)# dp[i]表示花i元能获得的最大喜爱度for_inrange(n):price,count,love=map(int,input().split())# 二进制优化多重背包k=1whilecount>0:cnt=min(k,count)cost=cnt*price value=cnt*love count-=cnt k<<=1forjinrange(x,cost-1,-1):dp[j]=max(dp[j],dp[j-cost]+value)print(dp[x])JavaScript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputLines=[];rl.on("line",line=>{inputLines.push(line.trim());});rl.on("close",()=>{let[x,n]=inputLines[0].split(" ").map(Number);letdp=Array(x+1).fill(0);for(leti=0;i<n;i++){let[price,count,love]=inputLines[i+1].split(" ").map(Number);// 二进制优化多重背包letk=1;while(count>0){letcnt=Math.min(k,count);letcost=cnt*price;letvalue=cnt*love;count-=cnt;k<<=1;for(letj=x;j>=cost;j--){dp[j]=Math.max(dp[j],dp[j-cost]+value);}}}console.log(dp[x]);});Go
packagemainimport("bufio""fmt""os")funcmain(){reader:=bufio.NewReader(os.Stdin)varx,nintfmt.Fscan(reader,&x,&n)dp:=make([]int,x+1)// dp[i]表示花i元能获得的最大喜爱度fori:=0;i<n;i++{varprice,count,loveintfmt.Fscan(reader,&price,&count,&love)// 二进制优化多重背包k:=1forcount>0{cnt:=min(k,count)cost:=cnt*price value:=cnt*love count-=cnt k<<=1forj:=x;j>=cost;j--{ifdp[j]<dp[j-cost]+value{dp[j]=dp[j-cost]+value}}}}fmt.Println(dp[x])}funcmin(a,bint)int{ifa<b{returna}returnb}
)
