beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

HDU_2955_ROBBERY

Posted on 2011-09-09 13:47 成幸毅 阅读(196) 评论(0)  编辑 收藏 引用
总结:可以从这里知道,0-1背包问题,价值和重量可以交换,对于其中只要一个为整型就可以解决
#include <iostream>
#include 
<cstdio>
#include 
<cstdlib>
using namespace std;

const int MAXN = 110;

double f[100000];
int w[MAXN];
double v[MAXN];
int main() {
    
    
int cas;
    scanf(
"%d",&cas);
    
while(cas--{
       
double p;
       
int n;
       scanf(
"%lf%d",&p,&n);
       
int sum = 0;
       
for(int i = 0; i < n; i++{
          scanf(
"%d%lf",&w[i],&v[i]);
          sum 
+= w[i];
       }

       
       memset(f,
0,sizeof(f));
       
       f[
0= 1;
       
for(int i = 0; i < n; i++)
         
for(int j = sum; j >= w[i]; j--{
            f[j] 
= max(f[j],f[j-w[i]]*(1-v[i]));
         }
 
       
       
for(int j = sum; j >= 0; j--{
          
if(f[j] > 1 - p) {
             cout
<<j<<endl;
             
break;
          }

       }

    }

    
  
//  system("pause");
    return 0;
}



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