ACdreamoj1110(多重背包) - c++编程基础

TOP

ACdreamoj1110(多重背包)

2015-07-24 06:13:18 来源: 作者: 【大中小】浏览:8次

题意：裸的多重背包，水题。

解法：和完全背包一样，只不过加一个数组，记录着每个物品用过的次数，多于存储量时就pass不更新。

还有一种方法是将每个物品用二进制压缩处理，第一个代码比较简单；

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const int INF=1000000007; int a[103]; int num[103]; int rem[Max]; bool ans[Max]; int n,cap; int main() { int t; //cout<
              
               cap||rem[j]>=num[i]) continue; if(ans[j]) { if(ans[j+a[i]]) { rem[j+a[i]]=min(rem[j+a[i]],rem[j]+1); continue; } ans[j+a[i]]=1; rem[j+a[i]]=rem[j]+1; } } } int out=0; for(int i=1; i<=cap; i++) if(ans[i]) out++; printf("Case %d: %d\n",kk++,out); } return 0; } /* 4 100000 1 12 456 5678 5 5 5 5 */


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：交换排序：冒泡排序	下一篇：DM8168 PWM驱动与测试程序

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: