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 阅读(1648) 评论(0)  编辑 收藏 引用


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