The Fourth Dimension Space

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

POJ 1384 Piggy-Bank 完全背包

重温了下 背包九讲 不仅发现了其中的一些错误 也发现了这篇文章的局限性,例如这个题。。。做完之后 我对背包的概念又模糊了。。。
#include<iostream>
using namespace std;

int dp[10001];
int w[10001];
int v[10001];
int main()
{

    
int t;
    
int e,f;
    
int n;
    
int ww;
    scanf(
"%d",&t);
    
int i,j,k;
    
for(i=1;i<=t;i++)
    
{
        scanf(
"%d%d",&e,&f);
        ww
=f-e;
        scanf(
"%d",&n);
        
for(j=1;j<=n;j++)
            scanf(
"%d%d",&v[j],&w[j]);
        memset(dp,
-1,sizeof(dp));
        dp[
0]=0;
        
for(j=1;j<=n;j++)
        
{

            
for(k=0;k<=ww-w[j];k++)
            
{

                
if(dp[k]!=-1)
                
{

                    
if(dp[k+w[j]]==-1)
                        dp[k
+w[j]]=dp[k]+v[j];
                    
else
                        dp[k
+w[j]]=min(dp[k+w[j]],dp[k]+v[j]);
                }

            }

        }

        
if(dp[ww]==-1)
            printf(
"This is impossible.\n");
        
else
            printf(
"The minimum amount of money in the piggy-bank is %d.\n",dp[ww]);





    }

    
return 0;
}

posted on 2010-03-08 21:19 abilitytao 阅读(1596) 评论(2)  编辑 收藏 引用

评论

# re: POJ 1384 Piggy-Bank 完全背包 2010-07-20 22:46 zoio

good !  回复  更多评论   

# re: POJ 1384 Piggy-Bank 完全背包 2010-08-23 13:27

加油!  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理