The Fourth Dimension Space

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

POJ 3624-Charm Bracelet 简单的0/1背包问题

经典的背包问题.

#include <iostream>
#include 
<algorithm>
using namespace std;

int w[3500];
int v[3500];
int dp[13000];


int main ()
{

    
int n,m;
    
int i,j;
    scanf(
"%d%d",&n,&m);
    
for(i=1;i<=n;i++)
    {

        scanf(
"%d%d",&w[i],&v[i]);

    }
    memset(dp,
0,sizeof(dp));
    
for(i=1;i<=n;i++)
    {

        
for(j=m;j>=w[i];j--)
        {

            
if(dp[j]<dp[j-w[i]]+v[i])
                dp[j]
=dp[j-w[i]]+v[i];
        }
    }
    printf(
"%d\n",dp[m]);
    
return 0;


}

posted on 2009-02-19 21:16 abilitytao 阅读(1987) 评论(3)  编辑 收藏 引用

评论

# re: POJ 3624-Charm Bracelet 简单的0/1背包问题 2009-03-15 13:58 cat

那个....memset貌似只能初始化char型数组吧.全局变量是自动初始化的...应该去掉那句.  回复  更多评论   

# re: POJ 3624-Charm Bracelet 简单的0/1背包问题[未登录] 2009-03-15 17:17 abilitytao

@cat
有道理 不过清零应该没有问题 如果是其它的数字就会错误了
  回复  更多评论   

# re: POJ 3624-Charm Bracelet 简单的0/1背包问题 2010-05-07 12:48 Cre_nws

@cat:因为,menset()的操作的基本单位时字节,而char型数据一般是一个字节,所以一般我们用于初始化char型数组,但是,在不引起错误的情况下,我们可以用它实现对整形的初始化,当然这时候我们只能有两个选择,0或-1
  回复  更多评论   


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