当前位置:网站首页>Knapsack problem acwing 9 Group knapsack problem
Knapsack problem acwing 9 Group knapsack problem
2022-07-05 06:24:00 【T_ Y_ F666】
knapsack problem AcWing 9. Group knapsack problem
Original link
AcWing 9. Group knapsack problem
Algorithm tags
knapsack problem DP
Ideas
Code
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 105;
int s[N];
int v[N][N], w[N][N],f[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read(), vv=read();
rep(i, 1, n+1){
s[i]=read();
rep(j, 0, s[i]){
v[i][j]=read(), w[i][j]=read();
}
}
// n Group items
rep(i, 1, n+1){
// The remaining capacity of the backpack Because items can only be used once So cycle from large to small
Rep(j, vv, 0){
// The first i Select an item in the group to maximize the value
rep(k, 0, s[i]){
if(v[i][k]<=j){
f[j]=max(f[j], f[j-v[i][k]]+w[i][k]);
}
}
}
}
printf("%lld", f[vv]);
return 0;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- New title of module a of "PanYun Cup" secondary vocational network security skills competition
- 区间问题 AcWing 906. 区间分组
- Liunx starts redis
- AE tutorial - path growth animation
- Redis publish subscribe command line implementation
- 1.15 - input and output system
- 7.Oracle-表结构
- 博弈论 AcWing 893. 集合-Nim游戏
- Chart. JS - Format Y axis - chart js - Formatting Y axis
- P3265 [jloi2015] equipment purchase
猜你喜欢
Install opencv -- CONDA to establish a virtual environment and add the kernel of this environment in jupyter
7.Oracle-表结构
1.手动创建Oracle数据库
LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively
博弈论 AcWing 893. 集合-Nim游戏
求组合数 AcWing 887. 求组合数 III
Matrixdb V4.5.0 was launched with a new mars2 storage engine!
Sqlmap tutorial (II) practical skills I
MySQL advanced part 2: MySQL architecture
阿里巴巴成立企业数智服务公司“瓴羊”,聚焦企业数字化增长
随机推荐
MPLS experiment
June 29, 2022 daily
Navicat连接Oracle数据库报错ORA-28547或ORA-03135
Leetcode stack related
TypeScript 基础讲解
MySQL advanced part 1: index
MySQL怎么运行的系列(八)14张图说明白MySQL事务原子性和undo日志原理
阿里巴巴成立企业数智服务公司“瓴羊”,聚焦企业数字化增长
[rust notes] 16 input and output (Part 1)
RecyclerView的应用
容斥原理 AcWing 890. 能被整除的数
求组合数 AcWing 887. 求组合数 III
WordPress switches the page, and the domain name changes back to the IP address
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
5. Oracle tablespace
Chart. JS - Format Y axis - chart js - Formatting Y axis
International Open Source firmware Foundation (osff) organization
Series of how MySQL works (VIII) 14 figures explain the atomicity of MySQL transactions and the principle of undo logging
[wustctf2020] plain_ WP
Winter messenger 2