2332: 【入门】环游世界之背包问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
张老师准备环游世界，出发之前要做的最重要的事情，当然是整理自己的背包啦。张老师有一个容积为m的背包 ，有n个物品作为放入背包的待选物品 ，每样东西都有自己的价值Wi，和体积Vi ，第i个物品有Ni个 （Ni=0时表示有无限多个），请你编程帮助张老师计算，他的背包能够存入的最大价值是多少？
30%数据满足 1 <= m,n <=1000
100%数据满足 1 <=m,n <= 10000
输入
第1行有2个整数N,M，表示物品的种类和背包的容积；
第2-N+1行，每行有3个整数Vi，Wi，Pi，分别表示每个物品的体积，价值，个数。（体积<=5000,价值<=5000,个数<=1000）
第2-N+1行，每行有3个整数Vi，Wi，Pi，分别表示每个物品的体积，价值，个数。（体积<=5000,价值<=5000,个数<=1000）
输出
一个整数，表示能够存入背包的最大价值。
样例输入 复制
5 50
1 1 50
2 4 3
48 49 1
1 51 1
3 3 3样例输出 复制
106提示
题目分析
这是多重背包问题： n 种物品，背包容量 m；每种物品 i：体积\(V_i\)，价值\(W_i\)，数量\(P_i\)； \(P_i=0\)代表无限个（完全背包）。 数据范围：\(n,m\le 10000\)，物品数量\(P_i\le1000\)。
优化方案：二进制拆分，把多重背包拆成 01 背包，\(P_i=0\)单独按完全背包处理。
状态：\(dp[j]\) 表示背包体积 j 能装的最大价值。 一维数组，逆序遍历（01 背包），顺序遍历（完全背包）。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXM = 10005;
int dp[MAXM];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
int v, w, p;
cin >> v >> w >> p;
if(p == 0)
{
// 完全背包：顺序
for(int j = v; j <= m; j++)
{
dp[j] = max(dp[j], dp[j - v] + w);
}
}
else
{
// 二进制拆分
int k = 1;
int cnt = p;
while(cnt > 0)
{
int take = min(k, cnt);
int tv = take * v;
int tw = take * w;
// 01背包逆序
for(int j = m; j >= tv; j--)
{
dp[j] = max(dp[j], dp[j - tv] + tw);
}
cnt -= take;
k *= 2;
}
}
}
cout << dp[m] << endl;
return 0;
}