大家好,又见面了,我是全栈君。
博客。
再加上这题体积与价值相等那么就更好做了。仅仅有 j %v[ i ] 余数同样的才干够同一时候处理(j 指的是某个体积的值),在计算某个数的时候,仅仅要计算前面的同样的余数中(在个数限制内)是否有 true(有放满的) 就能够了。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT long long int #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int mod = 1000000007 ; const int MY = (1<<5) + 5 ; const int MX = 100010 + 5 ; int n ,W ,ans ; int v[MX] ,num[MX] ; bool deq[MX] ,dp[MX] ; void input() { memset(dp ,false ,sizeof(dp)) ; for(int i = 1 ;i <= n ; ++i) scanf("%d" ,&v[i]) ; for(int i = 1 ;i <= n ; ++i) scanf("%d" ,&num[i]) ; } void DP(int v ,int num) { if(!num || !v) return ; if(num == 1) // 01 背包 { for(int i = W ;i >= v ; --i) if(!dp[i] && dp[i-v]) dp[i] = true ,ans++ ; } else if(num * v >= W) // 全然背包 { for(int i = v ;i <= W ; ++i) if(!dp[i] && dp[i-v]) dp[i] = true ,ans++ ; } else { num = min(num ,W/v) ; for(int a = 0 ;a < v ; ++a) // 同样余数一块处理 { int front =0 ,end = 0 ,sum = 0 ; for(int j = a ;j <= W ; j += v) { if(end - front-1 == num) // 去除过时元素 ,由于最多选择num[i] 个 sum -= deq[front++] ; deq[end++] = dp[j] ; // 存入 sum += dp[j] ; if(!dp[j] && sum) dp[j] = true ,ans++ ; } } } } int main() { //freopen("input.txt" ,"r" ,stdin) ; while(scanf("%d%d" ,&n ,&W) ,n+W) { input() ; dp[0] = true ; ans = 0 ; for(int i = 1 ;i <= n ; ++i) DP(v[i] ,num[i]) ; printf("%d\n" ,ans) ; } return 0 ; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116515.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...