The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2392-Space Elevator 背包问题(多重背包)

最近好像跟背包问题有缘啊,已经做了好几道了。不过感觉这个问题确有它值得研究之处,也从中学到不少东西呵&

这道题目的大意是:有n种材料,每种材料有数量c和长度h还有一个特殊限制(可以看成一个背包的容量)
出题者要你求出用这n种材料可以累加出的最大长度而且其中的每一种材料中的任何一个元素都不能高过这个限制a.想了想,貌似可以用多重背包来形容这个问题,当然我是非专业的,说得不恰当还请大家原谅;

下面的这段代码中有几点值得注意:
首先是这道题中的关键部分和我写的1276题非常相似(参考了网路上大牛的代码 先谢过~)
通过这两个题我发现:这种方法只适用于(这里我们用背包问题的原始定义来形象的说明)物品的重量等于其价值的情况;
非这种情况那就请老老实实按书上的方法做吧(如果说错了 还望您指出,不过我是这样认为的);
这种方法确实很快,而且比课本上提到的dp方法更牛,一定要掌握呵&

其次是这道题一定要先排序,再dp;
为什么呢?我想了想 给出下面一个例子:
如果数据是这样的:
2
7 40 3
5 23 1
如果不排序 那么按照那个算法26是不可及的
但是如果排序(按a从小到大)
变成
5 23 1
7 40 3
那么26就可能了
是不是很神奇?但这就是区别 所以本题必须要排序;
我后来又想了想 发现这其实是一个策略的问题,在实际中,我们也当然会把安全的部分放在底层,这总方法感觉上就更稳妥些,而且也带有某种贪心的性质我觉得。
如果哲学的来理解,我引用一句经典的话:九层之台,起于累土,千里之行,始于足下。呵呵,我感觉还挺符合本题的,不知道您觉得呢?

AC CODE:
#include <iostream>
#include
<cmath>
#include
<algorithm>
#include
<cstdio>
using namespace std;

struct node
{

    
int h;
    
int a;
    
int c;
}
a[401];

int cmp(node a,node b)
{
    
return a.a<b.a;
}



bool dp[40001];


int main ()
{

    
int n;
    
int i,j,k;
    scanf(
"%d",&n);

    
for(i=1;i<=n;i++)
    
{
        scanf(
"%d%d%d",&a[i].h,&a[i].a,&a[i].c);
    }

    sort(a
+1,a+1+n,cmp);
    
    
    
int max=0;
    dp[
0]=true;
    
for(i=1;i<=n;i++)
    
{
        
for(k=max;k>=0;k--)
            
if(dp[k]==true)
            
{
                    
for(j=1;j<=a[i].c;j++)
                
{

                    
int temp;
                    temp
=k+j*a[i].h;
                    
if(temp>a[i].a)
                        
break;
                    dp[temp]
=true;
                    
if(temp>max)
                        max
=temp;



                }

            }

        


    }

        printf(
"%d\n",max);
        
return 0;


    



}








posted on 2009-02-22 01:03 abilitytao 阅读(2132) 评论(6)  编辑 收藏 引用

评论

# re: POJ 2392-Space Elevator 背包问题(多重背包) 2009-03-09 21:09 金剑

按从大到小排,题目给的数据都不能过,不是么?  回复  更多评论   

# re: POJ 2392-Space Elevator 背包问题(多重背包) 2009-03-09 21:16 金剑

7 40 3
5 23 8
2 52 6

排后

5 23 8
7 40 3
2 52 6

5*4+2*7+2*6=46
而正确解应该是
5*3+7*3+2*6=48


我是看见你写得思路(没看程序)然后自己写了个程序,结果WA。问问
  回复  更多评论   

# re: POJ 2392-Space Elevator 背包问题(多重背包)[未登录] 2009-03-09 22:34 abilitytao

我的程序运行显示 你给出的数据答案是48...可能你细节上处理有问题吧  回复  更多评论   

# re: POJ 2392-Space Elevator 背包问题(多重背包) 2009-03-13 14:50 金剑

原来是这样
| 1st:
| 0 5 10 15 20
| 2nd:
| 7 12 17 22 27
| 14 19 24 29 34
| 21 26 31 36
|
| 3rd
↓ .................
.................

不好意思用你博客打了个草稿

  回复  更多评论   

# re: POJ 2392-Space Elevator 背包问题(多重背包)[未登录] 2009-03-13 17:17 abilitytao

呵呵 没关系 我很乐意和你探讨 如果还需要交流的话加我的qq:64076241  回复  更多评论   

# re: POJ 2392-Space Elevator 背包问题(多重背包) 2011-03-03 19:45 123456

解释真得很好。。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理