多重背包空间优化

 

有N种物品,第i种物品的体积是Ci,价值是Wi,每种物品的数量都是有限的,为ni..现有容量为V的背包,请你放入若干物品,在总体积不超过V的条件下,使总价值尽可能大。

int main(){ int N, V; cin >> N >> V; for(int i = 1; i <= N; i++) cin >> w[i] >> c[i] >> n[i]; for(int i = 1; i <= N; i++) for(int j = V; j >= 0; j--) for(int k = 0; k <= n[i]; k++) if(k*c[i] <= j) dp2[j] = max(dp2[j], dp2[j - c[i]*k] + w[i]*k); cout << dp2[V]; return 0; }