포켓 2755
신기한 주머니가 있는데, 총 부피는 40이고, 이 주머니로 약간의 물건을 변형시킬 수 있으며, 이 물건들의 총 부피는 반드시 40이어야 한다.John은 현재 n개의 원하는 물품을 가지고 있으며, 각 물품의 부피는 각각 a1, a2... an이다.John은 이 물건들 중에서 몇 가지를 선택할 수 있다. 만약 선택한 물체의 총 부피가 40이라면 이 신기한 주머니를 이용하면 John은 이 물건들을 얻을 수 있다.지금의 문제는 John이 물건을 선택하는 방식이 얼마나 다른가이다.
입력의 첫 번째 줄은 정수 n(1<=n<=20)으로 서로 다른 물품의 수를 나타낸다.다음 n줄은 줄마다 1에서 40 사이의 정수가 있는데 각각 a1, a2......an의 값을 제시한다.
선택한 아이템을 출력하는 방식에 따라 수량을 출력합니다.
샘플 입력 3 20 20 20 20 20
샘플 출력 3
간단한 dp로 추이 방정식을 f[i][j]=f[i][j-1]+f[i-v[j][j]][j-1]로 쓰기 쉽고 그 중에서 v[j]는 물품 j의 가치이다.또한 이 dp는 사실상 스캐닝의 단조성을 이용하여 f의 1차원을 계속 업데이트할 수 있고 f를 2차원으로 바꿀 필요가 없기 때문에 본 문제는 거의 0/1백팩과 유사하다.
Accepted 260kB 0ms 361 B G++
#include<stdio.h>
long long int f[41][21];
int n,v[21];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&v[i]);
f[0][0]=1;
for (int i=1;i<=40;i++)
f[i][0]=0;
for (int j=1;j<=n;j++)
{
for (int i=0;i<=40;i++)
f[i][j]=f[i][j-1];
for (int i=40-v[j];i>=0;i--)
f[i+v[j]][j]+=f[i][j-1];
}
printf("%lld
",f[40][n]);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
