当前位置:网站首页>ACdreamoj1110(多重背包)
ACdreamoj1110(多重背包)
2022-07-06 12:55:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
意甲冠军:多个裸露的双肩背包。水的问题。
解决方法:然背包一样,仅仅只是加一个数组,记录着每一个物品用过的次数,多于存储量时就pass不更新。
另一种方法是将每一个物品用二进制压缩处理。第一个代码比較简单;
代码:
/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;
#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const int INF=1000000007;
int a[103];
int num[103];
int rem[Max];
bool ans[Max];
int n,cap;
int main()
{
int t;
//cout<<pow(6,4)-1<<endl;
scanf("%d",&t);int kk=1;
while(t--)
{
memset(ans,0,sizeof ans);
scanf("%d%d",&n,&cap);
for(int i=0; i<n; i++)
scanf("%d",a+i);
for(int i=0; i<n; i++)
scanf("%d",num+i);
ans[0]=1;
for(int i=0; i<n; i++)
{
memset(rem,0,sizeof rem);
for(int j=0; j<=cap; j++)
{
if(j+a[i]>cap||rem[j]>=num[i])
continue;
if(ans[j])
{
if(ans[j+a[i]])
{
rem[j+a[i]]=min(rem[j+a[i]],rem[j]+1);
continue;
}
ans[j+a[i]]=1;
rem[j+a[i]]=rem[j]+1;
}
}
}
int out=0;
for(int i=1; i<=cap; i++)
if(ans[i])
out++;
printf("Case %d: %d\n",kk++,out);
}
return 0;
}
/*
4 100000
1 12 456 5678
5 5 5 5
*/
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117094.html原文链接:https://javaforall.cn
边栏推荐
- What is the problem with the SQL group by statement
- 20220211 failure - maximum amount of data supported by mongodb
- What are RDB and AOF
- [200 opencv routines] 220 Mosaic the image
- R语言可视化两个以上的分类(类别)变量之间的关系、使用vcd包中的Mosaic函数创建马赛克图( Mosaic plots)、分别可视化两个、三个、四个分类变量的关系的马赛克图
- 硬件开发笔记(十): 硬件开发基本流程,制作一个USB转RS232的模块(九):创建CH340G/MAX232封装库sop-16并关联原理图元器件
- Common English vocabulary that every programmer must master (recommended Collection)
- Opencv learning example code 3.2.3 image binarization
- Swagger UI教程 API 文档神器
- Huawei device command
猜你喜欢
KDD 2022 | 通过知识增强的提示学习实现统一的对话式推荐
Study notes of grain Mall - phase I: Project Introduction
Pinduoduo lost the lawsuit, and the case of bargain price difference of 0.9% was sentenced; Wechat internal test, the same mobile phone number can register two account functions; 2022 fields Awards an
MLP (multilayer perceptron neural network) is a multilayer fully connected neural network model.
What key progress has been made in deep learning in 2021?
Variable star --- article module (1)
HMS core machine learning service creates a new "sound" state of simultaneous interpreting translation, and AI makes international exchanges smoother
Introduction to the use of SAP Fiori application index tool and SAP Fiori tools
爱可可AI前沿推介(7.6)
15 millions d'employés sont faciles à gérer et la base de données native du cloud gaussdb rend le Bureau des RH plus efficace
随机推荐
快过年了,心也懒了
Taylor series fast Fourier transform (FFT)
性能测试过程和计划
Pat 1078 hashing (25 points) ⼆ times ⽅ exploration method
1_ Introduction to go language
15 millions d'employés sont faciles à gérer et la base de données native du cloud gaussdb rend le Bureau des RH plus efficace
KDD 2022 | 通过知识增强的提示学习实现统一的对话式推荐
字符串的使用方法之startwith()-以XX开头、endsWith()-以XX结尾、trim()-删除两端空格
Simple continuous viewing PTA
None of the strongest kings in the monitoring industry!
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
After working for 5 years, this experience is left when you reach P7. You have helped your friends get 10 offers
Laravel notes - add the function of locking accounts after 5 login failures in user-defined login (improve system security)
Study notes of grain Mall - phase I: Project Introduction
The most comprehensive new database in the whole network, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, flying Book Multidimensional table, heipayun, Zhix
监控界的最强王者,没有之一!
【mysql】游标的基本使用
【论文解读】用于白内障分级/分类的机器学习技术
【微信小程序】运行机制和更新机制
Opencv learning example code 3.2.3 image binarization