题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191
标准的多重背包
题目
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
复杂度是O(V*Σn[i])。
转化为01背包问题
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map> using namespace std; #define met(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define N 2310 int c[N], w[N], k; void slove(int cost, int weight, int cnt)///二进制思想，把cnt分成1,2,4,8,16......存入c中和w中，//按01背包处理
{
int m = ;
while( cnt >= m)
{
c[k] = m*cost;
w[k++] = m*weight;
cnt -= m;
m = m*;
}
if(cnt>)
{
c[k] = cnt*cost;
w[k++] = cnt*weight;
}
} int main()
{
int T, V, n; int cost, weight, cnt, dp[N]; scanf("%d", &T); while(T--)
{
met(dp, ); met(c, ); met(w, ); k = ; scanf("%d %d", &V, &n); for(int i=; i<=n; i++)
{
scanf("%d %d %d", &cost, &weight, &cnt); slove(cost, weight, cnt);
}
for(int i=; i<k; i++)
{
for(int j=V; j>=c[i]; j--)
{
dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
}
}
printf("%d\n", dp[V]);
}
return ;
}