多重背包问题 I
解题思路
每种物品的数量是有限个,将每种物品按照其数量拆分成多个物品,每个拆分后的物品都有相同的重量和价值,但数量为1,这样就把这个问题转换成了01背包问题。
根据思路写出的代码
#include <stdio.h>
#include <stdlib.h>
int N, V, N_all;
int w[1010];
int v[1010];
int s[1010];
int dp[100 * 100 + 10][1010];
int max(int a, int b)
{
return (a > b) ? a : b;
}
int getINDEX(int num)
{
int INDEX = 0;
while (1)
{
num -= s[INDEX];
if (num <= 0)
{
break;
}
INDEX++;
}
return INDEX;
}
int main()
{
scanf("%d %d", &N, &V);
for (int i = 1; i <= N; i++)
{
scanf("%d %d %d", &(w[i]), &(v[i]), &(s[i]));
N_all += s[i];
}
for (int i = 1; i <= N_all; i++)
{
for (int j = 1; j <= V; j++)
{
if (j < w[getINDEX(i)])
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[getINDEX(i)]] + v[getINDEX(i)]);
}
}
}
if (0) // 调试输出
{
for (int i = 0; i <= N_all; i++)
{
for (int j = 0; j <= V; j++)
{
printf("%d ", dp[i][j]);
}
printf("\n");
}
}
printf("%d\n", dp[N_all][V]);
return 0;
}