HDU 2191 다중 팩 문제
1799 단어 다중 배낭dpcsdnhdu2191ACM - 기본 dp
if (j < w[i])
dp(i, j) = dp(i - 1, j);
else
dp(i, j) = max(dp(i - 1, j - k * w[i]) + k * v[i]) (j - k * w[i] >= 0)
스크롤 배열을 사용하여 다음과 같은 코드를 계산합니다.
#include
#include
#include
#include
#include
#include
#include
#define MAX_N 1005
#define INF 0x3f3f3f
using namespace std;
typedef long long int ll;
int dp[MAX_N];
void ZeroOnePack(int weight, int value, int V)
{
for (int i = V; i >= weight; i--)
dp[i] = max(dp[i], dp[i - weight] + value);
}
void CompletePack(int weight, int value, int V)
{
for (int i = weight; i <= V; i++)
dp[i] = max(dp[i], dp[i - weight] + value);
}
int MultiplePack(int n, int* weight, int* value, int* num, int V)
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
if (weight[i] * num[i] > V)
CompletePack(weight[i], value[i], V);
else
{
int k = 1;
while (k < num[i])
{
ZeroOnePack(k * weight[i], k * value[i], V);
num[i] -= k;
k <<= 1;
}
ZeroOnePack(num[i] * weight[i], num[i] * value[i], V);
}
}
return dp[V];
}
int main()
{
//freopen("1.txt", "r", stdin);
int V, n, T;
int weight[MAX_N], value[MAX_N], num[MAX_N];
cin >> T;
while (T--)
{
cin >> V >> n;
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &weight[i], &value[i], &num[i]);
cout << MultiplePack(n, weight, value, num, V) << endl;
}
return 0;
}