Proud Merchants

题目描述

Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was $P_i$, but they would refuse to make a trade with you if your money were less than $Q_i$, and iSea evaluated every item a value $V_i$.
If he had $M$ units of money, what’s the maximum value iSea could get?

$1 \le N \le 500, 1 \le M \le 5000$
$1 \le Pi \le Qi \le 100, 1 \le Vi \le 1000$

题意

有$n$件商品和$m$单位的货币,每件商品的价格为$p_i$,价值为$v_i$,只有在拥有$q_i$单位的货币时才能购买它,求能够得到的最大价值总和

代码

这道题我尝试写了两种状态转移方程,都能A掉!
然后愉快地浪费了三节晚自习

[一]网上流传式

假设我们现在有$i$和$j$两种物品
可以看出,装完$i$之后能不能装$j$取决于背包有没有$p_i+q_j$
装完$j$之后能不能装$i$取决于背包有没有$p_j+q_i$

因为2种顺序的总价值是一样的
所以我们应该选择$p_i+q_j$和$p_j+q_i$里面较小的那个数所对应的顺序

状态转移方程如下

1
2
3
4
5
6
memset(f, 0, sizeof(f));
for(int i = 1; i <= x; ++ i){
for(int j = y; j >= m[i].q; -- j){
f[j] = max(f[j], f[j - m[i].p] + m[i].v);
}
}

$f[j]$指拥有$j$元钱时能得到的最大价值

所以转移的时候$j$的下界为$m[i].q$
由题意,这很容易理解

我们可以看出状态$f[j]$由状态$f[j-m[i].p]$转移而来
也就是说,我们要保证$f[j-m[i].p]$在当前是最优解,才能转移出最优的$f[j]$.

我们又发现$f[j]$能拿来转移的最小值为$m[i].q-m[i].p$
也就是说,按照$m[i].q-m[i].p$排序能保证转移的正确性

1
2
3
4
//c = q-p
inline bool cmp(const M&a, const M&b){
return a.c < b.c;
}
[二]CSYdalao式

这是最初想了很久没有想通,然后在$csy dalao$的帮助下得到的第二种做法

我们先把他给出的诡异的状态转移方程列出来

1
2
3
4
5
for(int i = 1; i <= n; ++ i){
for(int j = m + p[i] - q[i]; j >= p[i]; -- j){
dp[j] = max(dp[j], dp[j - p[i]] + v[i]);
}
}

$dp[j]$指花费j元钱能得到的最大价值

$j$的循环下界是很容易想到的
至于它的循环上界为什么是$m + p[i] - q[i]$,$csy dalao$给出了一个非常精妙的解释

因为状态$dp[j]$从状态$dp[j - p[i]]$转移而来
意思是花了$j$元所能得到的最大价值
所以我们可以理解为当前已经花了$j-p[i]$元钱了
这等价于,我们手里还有$m-(j-p[i])$元钱.
而由题目的限制条件可以发现,$m-j+p[i]$是要大于$q[i]$的
所以不等式两边移一下项,就能得出它的上界$m+p[i]-q[i]$了

由于这里$j$能转移到的上界为$m-p[i]+q[i]$
所以按照$p[i]-p[j]$的降序排列,也就是按照$-p[i]+q[i]$的升序排列
能保证随着$i$的增加,能转移到的状态的上界是不断增加的
这样,后面的状态才能顺利地从前面的状态转移而来.

1
2
3
inline bool cmp(const M&a, const M&b){
return a.c > b.c;
}

另外,因为这里要保证完全装满背包,所以要稍微加点初始化

1
2
memset(dp, 128, sizeof(dp);
dp[0] = 0;