01背包基础

关键词：

The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university. 


For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible. 


His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.

InputThe first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj . 
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .OutputFor each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set. 

Notes and Constraints 
0 < T <= 100 
0.0 <= P <= 1.0 
0 < N <= 100 
0 < Mj <= 100 
0.0 <= Pj <= 1.0 
 A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.Sample Input

3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05

Sample Output

2
4
6

• 题意:其实这道题还是很坑的，就是有个人去抢银行了，每个银行可以抢的钱是Mj，抢钱被抓住的概率是Pj，给你一个最大被抓概率，问这时最多抢多少钱。

• 思路：这道题的关键在于一般情况下，我们用背包容量来表示dp的数位，这个题目中背包大小变成了浮点数，就只能反过来存，dp[获得钱数]=概率；最后从大到小输出第一个概率大于等于Pj的dp的标点

代码：

import java.util.Arrays;
import java.util.Scanner;

public class E {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t-->0){
        double v = sc.nextDouble();
        int n = sc.nextInt();
        double vo[] = new double[1050];
        int val[] = new int[1050];
        int sum = 0;
        for(int i=0;i<n;i++){
            val[i] = sc.nextInt();
            vo[i] = sc.nextDouble();
            sum+=val[i];
        }
        double[] dp = new double[10500];
        Arrays.fill(dp, 0);
        dp [0] = 1;
        for(int i=0;i<n;i++){
            for(int j=sum;j>=val[i];j--){
                dp[j] = Math.max(dp[j], dp[j-val[i]]*(1-vo[i]));
//                System.out.println(j+"  :"+dp[j]);
            }
        }
        for(int i=sum;i>=0;i--){
            if(dp[i]>=(1-v)){
                System.out.println(i);
                break;
            }
        }
        
    }
}
}

acwing（基础）---01背包和完全背包多重背包问题(代码片段)

初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候... 查看详情

动态规划基础-----01背包（总结）(代码片段)

1、动态规划（DP）　　动态规划（DynamicProgramming，DP）与分治区别在于划分的子问题是有重叠的，解过程中对于重叠的部分只要求解一次，记录下结果，其他子问题直接使用即可，减少了重复计算过程。 　　另外，DP在求解... 查看详情

动态规划问题3--多重背包(代码片段)

多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情

动态规划问题3--多重背包(代码片段)

多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情

01背包基础-空间优化（滚动数组，一维阵列）

2017-09-03 11:39:16writer：pprp以很简单的一个动态规划问题为引入：从左上角到右下角走过的路径和最大，问你最大为多少？1、可以想到普通的dp状态转移为： dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];2、采用滚动数组的方式-节约... 查看详情

01完全多重背包模板

背包问题：背包总容量为W，有n件重量为weight[i],权值为value[i]的物品1、01背包：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。1voidZeroOnePack(intweight,intvalue)2{3for(intw=W;w>=weight;w--)4dp[w]=max(dp[w-weight]+value,... 查看详情

01背包

01背包是动态规划中，最基础也是经典的一个算法之一。经典题意：1.有n个不同的物体，有体积为m的一个背包；2.n个物体分别有自己的体积v,价值c; 输出：在背包中能装的最大价值 题解：首先将这n个物体的体积和价值存... 查看详情

动态规划背包问题01背包完全背包多重背包

 一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情

动规基础——01背包问题(背包问题ⅱ)(代码片段)

题目来源：领扣|LintCode有i个物品和一个总容量为j的背包.给定数组weight表示每个物品的重量和数组value表示每个物品的价值，求最大价值。（物品不能分割）背包问题II这道题是一道动态规划(dp)算法的基础题，有两种实现方式，... 查看详情

进击的算法动态规划——01背包(代码片段)

🍿本文主题：动态规划01背包背包问题C/C++算法🎈更多算法：基础回溯算法基础动态规划💕我的主页：蓝色学者的主页文章目录一、前言二、概念✔️动态规划概念✔️01背包的概念三、问题描述与... 查看详情

背包问题专栏（01，完全，多重）(代码片段)

...的模板是套用了A.S.KirigiriKyouko的模板。请dalao见谅一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和... 查看详情

模板背包

（死亡）本文部分参照背包九讲（链接点这里）先看三道题：01背包，完全背包，混合背包请记住这个题面：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。有... 查看详情

基础dp背包(代码片段)

01背包P2871手链CharmBracelet#include<iostream>#include<cstdio>usingnamespacestd;#definetcl(a,b,c)for(a=b;a<=c;a++)#defineetc(a,b,c)for(a=b;a>=c;a--)constintmaxx=100001;intw[maxx],v[maxx] 查看详情

p1417烹调方案//基础背包卡longlong

我又一次失败了这道题看起来是01背包，但是有需要注意的地方对于这个我用一种易懂的方式说一下平常做01背包的题时，由于i的价值永远是不变的，所以i讨论的顺序对结果不影响但是这道题中，如果你先讨论了1号点，再讨论... 查看详情

背包问题

背包九讲--各种背包问题(2012-02-1515:34:21)转载▼标签：背包 分类：acmP01:01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且... 查看详情

代码随想录动态规划||完全背包基础518377

Day38完全背包理论基础完全背包有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值... 查看详情

hdu2602bonecollector(01背包dp)

...些物品的价值和体积，问你最大的价值。析：最基础的01背包，dp[i]表示体积i时最大价值。代码如下：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#include<string>#include<cstdlib>#include<cmath& 查看详情

动态规划入门-01背包问题-poj3624

2017-08-12 18:50:13writer：pprp对于最基础的动态规划01背包问题，都花了我好长时间去理解；poj3624是一个最基本的01背包问题：题意：给你N个物品，给你一个容量为M的背包　　给你每个物品的重量，Wi　　给你每个物品的价值，Di... 查看详情