题目描述
有N种物品和一个容量为V的背包。第i种物品的重量是w[i]，价值是c[i]，有k[i]个。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
输入描述
第一行为N，V。
下面N行，第i行描述第i种物品的w[i]，c[i]，k[i]，用一个空格分隔。
输出描述
输出只有一个数，最大总价值。
测试用例
输入
6 1
7 10 4
6 9 1
6 8 1
10 6 2
9 8 3
1 3 2
输出
3
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[500005], w[500005], c[500005], n, tw, tc, tk, v, idx = 0;
void addItem(ll tw, ll tc, ll tk) {
for (ll i = 1; i <= tk; i *= 2)
++idx, w[idx] = tw * i, c[idx] = tc * i, tk -= i;
if (tk > 0)
++idx, w[idx] = tw * tk, c[idx] = tc * tk;
}
int main() {
cin >> n >> v;
for (ll i = 1; i <= n; ++i)
scanf(" %lld%lld%lld", &tw, &tc, &tk), addItem(tw, tc, tk);
for (ll i = 1; i <= idx; ++i)
for (ll j = v; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
cout << dp[v];
}