分组背包
分组背包是LC(01)背包的一种变形吧。它就是给你一点质量，你不一定全部质量都要选，可以看看HDUOJ的Saving HDU，如果用01背包算出来就是3，用分组背包或者贪心算出来就是5
模板
//n为物品种类，v是背包容量，pi为物品价格，m为物品质量
//前面的i也得是1，不能是0
for(int i=1;
i<=n;
i++){
for(int j=v;
j>=0;
j--){
for(int k=1;
k<=m[i];
k++){
int t1=k,t2=k*pi[i];
if(j【分组背包】
Title
文章图片
某一水题
#include
#include
#include
using namespace std;
int n,t,w1[1000001],w2[1000001],t1[1000001],t2[1000001],dp[1000001];
int main(){
cin>>n>>t;
for(int i=0;
i>w1[i]>>t1[i]>>w2[i]>>t2[i];
for(int i=0;
i=min(t1[i],t2[i]);
j--){
if(t1[i]<=j)
dp[j]=max(dp[j],dp[j-t1[i]]+w1[i]);
else
dp[j]=max(dp[j],dp[j-t2[i]]+w2[i]);
}
cout< 推荐阅读
- 【golang】leetcode中级-字母异位词分组&无重复字符的最长子串
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #新中式宠妈艺术#我的双肩背包
- 斯坦福大学密码学公开课——分组加密的应用（一次性密钥）
- js对象数组(JSON)|js对象数组(JSON) 根据某个共同字段 分组
- Java数据结构和算法-动态规划算法解决背包问题
- SQL总结-开窗函数
- 冬季实战营 动手实战-云上多产品学习，使用ECS服务器部署MySQL数据库 领鼠标 云小宝 背包 无影
- 冬季实战营动手实战-上云必备环境准备，动手实操快速搭建LAMP环境 领鼠标 云小宝 背包 无影
- 拍乐云首发音视频「分组讨论」开放能力，开启线上群聊互动新玩法