首页 > 代码库 > HDU-3466-Proud Merchants
HDU-3466-Proud Merchants
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=3466
这题是个好题，之前没有想到得按先q-p来排序，因为q的原因，取得顺序不好就得不到最大价值。
看了OceanLight http://blog.csdn.net/oceanlight/article/details/7866759#comments 的博客
题意是： 给你一些钱 m ，然后在这个国家买东西， 共有 n 件物品，每件物品有 价格 P 价值 V 还有一个很特别的属性 Q, Q 指 你如过想买这件物品 你的手中至少有这钱Q 。 虽然你只要花费 钱P ，但你的手中至少有钱Q，如果不足Q ，不能买。问给你钱M ，列出N件物品，最多能获得多少价值的东西。。。。
第一眼看是个DP。。。。 但是想了许久都想不出 状态转移方程。。。
废话不多说。 给出解题思路。。。。。
解： 按 Q-P 的大小 ，从小到大排序，然后按照0-1 背包的思想
dp[c]=max(dp[c],dp[c-p[i]])+v[i]; 最终 dp[m]就是结果。
思路很简单，但是很难想。
在这我给出为什么要按Q-P排序的证明
一。 首先，不想为什么 ，要按照Q-P 排序。我们先想这么一个问题，（原因一会就知道了）。
给你n 个这种商品，你最少需要多少钱能够买下来。。(通过这个问题，可以找出一个性质)
再把这个商品转化 一下。。
还是有三个属性 P 价格 、V 价值 、 M 为Q-P。
Sum = P1 +P2 +P3 +........+Pn+max(Mi-(P(i+1)+P(i+2)+...........Pn))；
要使得Sum 最小 就应该按照 M从大到小排序 (这里就是从大到小，没错)，然后0-1背包求解。
证明：
如果看不懂公式 是什么 意思。。。没关系 那你就看 这样一个题的题解。。。这里有相同的公式（很简单的）
http://blog.csdn.net/oceanlight/article/details/7862104
这是我昨天写的一个题的题解，真没想到今天会用到的。。。
如果你看完了，你就应该懂了 。 要得到最小的sum ，就应该按照 M 从大到小排序了吧
也就是说我们应该先买M最大的物体，然后买M第二大的 。。。。。 最后买最小的。。。这个性质是这个问题的关键。
二。给一定的钱 ，我们的购买方式是 应该先买M最大的物体(M=Q-P)，然后依次买第二大、第三大、、、、、
我们已经知道这个购买方式，怎么实现就要用到DP 中的0-1背包的思想了。
dp[c]=max(dp[c],dp[c-p[i]])+v[i]; c 为第c 个物品。这是用一维数组实现01背包。。
dp[c-p[i]] 是指 我们在容量为c 的包中 放了p[i]之后 还能放的物品的价值。
i 从 1 到 n 。 dp[c-p[n]] 是放了 第n个物品后 还能放多少价值的物品。。。所以 P[n] 的M 值应该最大
通俗的说： 这个dp过程 正好是逆向的 。 dp[c-p[i]]是dp[c]的最优子结构。
所以 在DP 的时候我们应该按照 M的值从小到大排序。
也就是说我们应该按照 Q-P 的值 从小到 大排序在 DP 了。。。。
觉得对dp的理解深刻了一点，又感觉对dp不怎么理解了，
代码
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int p,q,v;
}me[505];
bool cmp(node a,node b)
{
return a.q-a.p<b.q-b.p;
}
int main(void)
{
int i,j,k,n,m;
int dp[5005];
while(scanf("%d%d",&n,&m)==2)
{
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
scanf("%d%d%d",&me[i].p,&me[i].q,&me[i].v);
sort(me,me+n,cmp);
for(i=0;i<n;i++)
{
for(j=m;j>=me[i].q;j--)
{
dp[j]=max(dp[j],dp[j-me[i].p]+me[i].v);
}
}
printf("%d\n",dp[m]);
}
return 0;
}
参数
62MS 368K 680 B
HDU-3466-Proud Merchants