首页 > 代码库 > 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