当前有N种物品,第i种物品的体积是Ci,价值是wi。每种物品的数量都是无限的,可以任意选择若干件。
现有容量为V的背包,请你放入若干物品,使总体积不超过V,并且总价值尽可能大。
这就是完全背包问题,和01背包的区别就是物品无限多个。
原始版本（不优化）
int main(){ int N, V; cin >> N >> V; for(int i = 1; i <= N; i++) cin >> w[i] >> c[i]; for(int i = 1; i <= N; i++)//枚举物品 for(int j = 0; j <= V; j++)//枚举当前背包容量 for(int k = 0; k*c[i] <= j; k++)//枚举当前物品数量 dp[i][j] = max(dp[i][j], dp[i-1][j - k*c[i]] + k*w[i]); cout << dp[N][V]; return 0; }
