• vivo2019提前批笔试第三题：
• 小v负责一次活动礼品采购每一款礼品的受欢迎程度(热度值)各不相同，现给出总金额以及各个礼品的单价
• 和热度值且每个礼品只购买一个，如何购買可以使得所有礼品的总热度值最高
• 第一行是一个正整数，表示总金额(不大于1000)
• 第二行是一个长度为n的正整数数组表示礼品单价(n不大于100)
• 苐三行是一个长度为n的正整数数组，表示对应礼品的热度值
• 一个正整数表示可以获得的最高总热度值

经典的0-1背包问题，可惜当时没做出來。
对于经典的0-1背包：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i], 价值是w[i]求解将哪些物品装入背包可使价值总和最大。
问题狀态定义dp[i][v]代表前i件物品放入一个容量为v的背包可以获得的最大价值因此有状态转移方程：
表示前i件物品放入容量为v的背包能获得的最大徝，要么是前i-1件物品放入容量为v的背包所能获得的最大值（第i件物品不放） 要么是前i-1件物品放入容量为v-c[i]的背包的最大值 + 第i件物品的价值（放入第i件物品）。