The Fourth Dimension Space

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

POJ 1837-Balance 0/1背包问题的扩展

//copyright by abilitytao
#include <iostream>
using namespace std;


int pos[21];
int weight[21];
int mid=4000;
int result[21][8000];
int c,g;


int main()
{

    int i,j,k;
    scanf("%d%d",&c,&g);
    for(i=1;i<=c;i++)
        scanf("%d",&pos[i]);
    for(i=1;i<=g;i++)
        scanf("%d",&weight[i]);
    for(i=1;i<=c;i++)
    {

        result[1][pos[i]*weight[1]+4000]++;
    }
    // 以上是dp初始化,接下来将用动态规划不断地挂上新的砝码；

    for(i=2;i<=g;i++)
    {

        for(j=1;j<=c;j++)
            for(k=1;k<=8000;k++)
            {

                if(result[i-1][k]!=0)
                result[i][k+weight[i]*pos[j]]+=result[i-1][k];
            }
    }
    printf("%d\n",result[g][4000]);

    return 0;
}




这个题目做的确实有点郁闷，说实话，我是参考网上的代码做的，即使如此，我还是没法证明那个状态转移方程的正确性；
只是感觉上像是对的，汗~后来联想到弗洛伊德和bellman-ford我这样说了：一切尽在迭代中啊~
如果有牛人能帮我证明一下的话 我感激不尽呵＆ 我的qq:64076241

再说说做这个题目的收获，那个+4000的小技巧倒是很受用，呵呵；
还有就是对动态规划的感觉越来越好了，有的时候能凭直觉把题做出来了...

posted on 2009-02-20 00:03 abilitytao 阅读(1642) 评论(0)  编辑 收藏 引用


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