DP_Training E. 01背包变型
题意
与01背包相同,(W)表示背包容量,(w_i)表示物品体积,(v_i)表示物品价值
[1leq N leq 100\
1leq W leq 10^9\
1leq w_i leq W\
1leq v_i leq 10^3
]
分析
我们知道01背包的复杂度是(O(nV))的,(V)是背包体积
但是此题的(V)很大。这显然是不行的,但是注意到(Nv_i)最多只有1e5,想到设计DP
(dp[i])表示价值达到(i)所需要的最小体积是多少,答案就是第一个(<=W)的(i)
转移方程
[dp[j] = min(dp[j - v[i]] + w[i])
]
代码
ll f[maxn];
ll w[maxn];
ll v[maxn];
int main(){
int n = rd();
int V = rd();
for(int i = 0;i < n;i++)
v[i] = rd(),w[i] = rd();
ll c = 0;
for(int i = 0;i < n;i++)
c += w[i];
for(int i = 0;i <= c;i++)
f[i] = 1e9;
f[0] = 0;
for(int i = 0;i < n;i++)
for(int j = c;j >= w[i];j--)
f[j] = min(f[j],f[j - w[i]] + v[i]);
for(int i = c;i >= 0;i--)
if(f[i] <= V) {
printf("%lld
",i);
break;
}
}