완전 가방【DP】
4078 단어 DP
> Input 첫 줄: 두 개의 정수, M(가방 용량, M<=200)과 N(아이템 수량, N<=30);두 번째...N+1줄: 줄마다 두 개의 정수 Wi,Ui로 각 물품의 무게와 가치를 나타낸다.
> Output은 최대 총 가치를 나타내는 행에 한 개만 표시됩니다.
> Sample Input 12 4 2 1 3 3 4 5 7 9
> Sample Output 15
> 문제풀이 아이디어 이 문제는 완전히 가방이 01가방으로 변할 수 있다.판단의'선택'을 같은 줄로 만들면 된다. 같은 종류의 물건을 많이 선택할 수 있기 때문이다.그래서 이렇게 간단한데 내가 주석을 한 번 해 볼게. 자꾸 주석을 하지 않아서 좀 당황스러워.근데 진짜 할 말이 없어요!
> 코드
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,w,p,f[205];
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w,&p);
for(int j=w;j<=m;j++)
f[j]=max(f[j],f[j-w]+p);
//
}
printf("%d",f[m]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
