本题为3月16日23上半学期集训每日一题中A题的题解
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1−5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为 \(v_j\) ，重要度为 \(w_j\) ，共选中了k件物品，编号依次为 \(j_1,j_2,\cdots,j_k\) ，则所求的总和为:\(v_{j_1} \times w_{j_1} + v_{j_2} \times w_{j_2} + \cdots + v_{j_k} \times w_{j_k}\).
请你帮助金明设计一个满足要求的购物单。
第一行，为2个正整数，用一个空格隔开：N m（其中N (<30000)表示总钱数，m(<25)为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格( \(v \leq 10000\) )，p表示该物品的重要度(1−5).
1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。
1000 5
800 2
400 5
300 5
400 3
200 2
3900
本题就是一个最基础的01背包的模型,只是此处每个商品的价值被定义为它的 \(价格 \times 优先级\) 而已,所以直接套用01背包的板子即可.
此处 $ N \times m < 750000$ ,故无需进行空间压缩,使用普通的01背包板子即可.当然你想空间压缩也是可行的.
如果你还不会01背包,请先阅读背包九讲(如果打不开github也可以在集训队的群文件中搜索),或者这篇博客(可能需要一点魔法才能访问)进行学习,当然也可自行搜索博客等学习.在ACWing上有公开的01背包的板子题,请尝试独立通过此题,然后再来做这道题.
时间复杂度: \(O(NM)\)
空间复杂度: \(O(NM)\)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
int *v = new int[m + 1]; // 价格
int *p = new int[m + 1]; // 优先级
for (int i = 1; i <= m; i++) {
cin >> v[i] >> p[i];
}
// 背包DP模板
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (j - v[i] >= 0) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i] * p[i]); // 此题中每个商品的价值是它的价格乘优先级
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[m][n] << "\n";
return 0;
}
"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德
背包是游戏中经常使用的一个组件，它负责管理玩家在游戏中所获得的道具。一个完整的背包系统应当具有将物品放置进背包、对背包内物品进行管理和使用背包内物品等功能。而往往一个背包系统的逻辑关系较为复杂，如果把所有功能都放在一个脚本中实现会使代码显得十分冗杂且缺乏逻辑。所以在背包系统的设计过程中，我们常将其分解为数据、逻辑和UI三部分分别来进行完成。一、UI设计以CottonPuzzle中的背包设计为例，我们需要有物品展示栏、物品切换按键和物品提示信息等部分。在Canvas中创建ItemHolder，在ItemHolder中创建LeftButton和RightButton控制物品的左右切换、Slot来控
【动态规划】一、背包问题1.背包问题总结1）动规四部曲：2）递推公式总结：3）遍历顺序总结：2.01背包1）二维dp数组代码实现2）一维dp数组代码实现3.完全背包代码实现4.多重背包代码实现一、背包问题1.背包问题总结暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！背包问题是动态规划（DynamicPlanning）里的非常重要的一部分,关于几种常见的背包，其关系如下：在解决背包问题的时候，我们通常都是按照如下五部来逐步分析，把这五部都搞透了，算是对动规来理解深入了。1）动规四部曲：（1）确定dp数组及其下标的含义（2）确定递推公式（3）dp数组的初始化（4）确定遍历顺
我一直在使用动态规划的这种变体来解决背包问题:KnapsackItem=Struct.new(:name,:cost,:value)KnapsackProblem=Struct.new(:items,:max_cost)defdynamic_programming_knapsack(problem)num_items=problem.items.sizeitems=problem.itemsmax_cost=problem.max_costcost_matrix=zeros(num_items,max_cost+1)num_items.timesdo|i|(max_cost+1).ti
518.零钱兑换II1.代码classSolution{public:intchange(intamount,vector&coins){vectorf(amount+1,0);f[0]=1;for(inti=0;i2.动规五部曲1.确定dp数组和其下标含义由题目说可知求选择钱票得到总和为target的方案数，dp[j]相当于选择物品体积相加为i的方案数2.递推公式每次加入物品，都有可能到达体积j,所以在每次加上这个物品到达j时加上这个方案数f[j]+=f[j-coins[i]];3.初始化因为在for循环和dp公式中没有确切的值，肯定需要初始化，初始化第一个就可以保证后面的推导出来了，f[0
我正在编写一个程序，以使用背包解决方案找到最佳的MLB阵容。为此，我传入了球员数据，其中包含球员计算出的值(value)和薪水。就背包问题而言，薪水将是我的“重量”。我的问题不是能够选择球员，而是选择最佳阵容。我要选择一个投手、一个中锋、一垒手、二垒手、三垒手、游击手和三名外野手。我可以成功地完成这一切。我希望我的“权重”是36,000，但我目前只选择一个总计21,000的阵容。这是我的背包代码:CalculateLineUp.prototype.findOptimalLineUp=function(data,capacity){varitems=data.data;varidxIte
今天只有1道题，属于动态规划的01背包问题的应用。首先理解一下动态规划的01背包问题。推荐一个视频，动态规划DP0-1背包，这是我认为讲得最为通透的。很多讲解动态背包问题的，一上来就画二维表格，遍历背包或者遍历容量，其实本质上，根本就看不懂那个二维表格是什么意思，为什么容量每次都要从0开始遍历。从原理上讲，容量从0开始只是一种假设，为的是让后面的背包如果装东西了，那么背包容量就会减少，再减少了容量后，怎么挑选物品才会使得质量最高，因此需要从0遍历，这些都是起了给后面的递归初始化一个值的作用。 小偷偷东西，有一个8容量背包，那么他开始从编号4开始偷（也可以从编号1开始偷），他有两种选择，偷或者不
我有一个项目，我需要对一个xml文件进行二进制64位编码并将其放入另一个xml中。为了让它工作，我首先使用dp:serialize序列化xml，然后对由此产生的变量使用dp:binary-encode。除了所有斯堪的纳维亚字符都被转义之外，这工作正常。当我解码结果时，åäö变成了åäö。有什么想法吗？我试过在输出标签上使用dp:escaping="minimum"(xsl:output标签会影响dp:serialize吗？)和许多其他选项。通过在二进制64位编码之前打印序列化结果，我看到在调用dp:serialize时添加了转义。是否可以在不转义数据电源的情况下进行序列化？
我想重命名子目录中的文件，文件名的已知部分是“.log”。当我尝试类似下面的操作时ren子目录\*.log*file2.txt或ren.\subdirectory\*.log*file2.txt我收到错误:命令的语法不正确。我在这里有两个问题:我是否总是需要在ren中给出完整路径？文件1的命令？如果是，那么如果我不想硬编码，我们如何给出完整路径？我知道我们可以使用'%~dp0'来获取当前目录路径，但我不确定如何将它与'ren'一起使用。 最佳答案 添加引号会起作用:ren"subdirectory\*.log*"file2.txt或
这个问题在这里已经有了答案:Whatdoes%~dp0mean,andhowdoesitwork?(7个答案)关闭5年前。.cmd文件中的pushd%~dp0是什么意思？我知道%~dp0表示它表示一个驱动器号。pushd表示什么？
我是脚本编写(尤其是powershell)的新手，也是StackOverflow的新手，所以请原谅我的无知，请多多包涵!我会尽我所能具体解释我想做什么，希望有人能详细说明我可以做些什么来让它发挥作用。预期流程/工作流程:一位同事下载了包含所有必需文件的“Install.zip”文件。此“Install.zip”文件包含“Setup.bat”文件(用于计算机配置)、“Fubar.zip”文件、2个powershell脚本和一个自定义powerplan(.pow)文件。下载后，他们将运行“Setup.bat”文件，它几乎可以完成所有工作。在该批处理文件中，它调用了2个powershell脚