知识点:多重背包,也就是一个物品有多个,然后求总价值。
算法竞赛上的板子题目:
链接:https://www.luogu.com.cn/problem/P1776
介绍二进制拆分优化
就是把几个完全相同的拆成1+2+4+...+2^n+mod,然后再进行dp的办法
代码:
重点在new_n,new_w,new_m这几个
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef unsigned long long ll;
using namespace std;
const int N = 1e5 + 10;
int n, C, dp[N], w[N], c[N], m[N];
int new_n;//二进制拆分后的新物品总数量
int new_w[N], new_c[N], new_m[N];//二进制拆分后的新物品
int main()
{
cin >> n >> C;
for (int i = 1; i < n + 1; i++)cin >> w[i] >> c[i] >> m[i];//价值,重量,数量
new_n = 0;
//二进制拆分
for (int i = 1; i <= n; i++)
{
//这里就是利用二进制的思想:把一个数拆成以最小二进制和它的余数表示:
//如把25 = 1 + 2 + 4 + 8 + 10
//意思就是把25个i物体看成1、2、4、8、10个物体的集合
for (int j = 1; j <= m[i]; j <<= 1)
{
m[i] -= j;
new_c[++new_n] = j * c[i];
new_w[new_n] = j * w[i];
}
if (m[i])
{
new_c[++new_n] = m[i] * c[i];
new_w[new_n] = m[i] * w[i];
}
}
//滚动数组版本的0/1背包
for (int i = 1; i <= new_n; i++)
for (int j = C; j >= new_c[i]; j--)//枚举背包容量
dp[j] = max(dp[j], dp[j - new_c[i]] + new_w[i]);
cout << dp[C];
return 0;
}
标签:int,二进制,P1776,拆分,new,筛选,include,宝物,dp
From: https://www.cnblogs.com/zzzsacmblog/p/18114066