hdu2844
분석:
배낭
이런 조합 방식을 겪었지만 n년이 지난 지금은 잊어버렸다.
1, 2, 4는 8보다 작은 모든 수를 조합할 수 있다.
1, 2, 4, 8은 16보다 작은 모든 수를 조합할 수 있다.
1, 2, 4, 8, 16은 32보다 작은 모든 수를 조합할 수 있다.
……
PS 1개:
또한 인터넷의 코드를 보면 거의 모두 dp[i]로 용량이 i라는 가방을 표시한다
얼마의 가치를 담을 수 있는지, 점차적인 공식은 dp[j]=MAX(dp[j], dp[j-val[i]]]+val[i]),
그리고 dp[i]가 ==i인지 아닌지를 판단하면 ans++와 같다.
이 방법에 대해 야채새는 애교를 부리며 잔소리를 한다.
1. flag[i]로 i 상태가 도달할 수 있는지 표시하면 됩니다. 용량이 i인 가방을 요구할 필요가 없습니다.
최대 몇 val 장착 가능;(그래서 내 코드에서 쓰는 게 (상태 now) = (상태 now)
||(상태 pre))
2、이 방법에 대해서 잘 이해하지 못하면 난폭한 일이 생기기 쉽다~~,
바로 다음과 같습니다.
"왜 내가 판단을 할 때 dp[i]>=i라는 식으로
이미if(dp[i]>=i)
ans++,
이런 방법으로 쓴 코드도 ac를 할 수 있을까요?
이런 문제의 출현.
이것에 대해 이 문제는 특례라고 할 수 있을 뿐이다. n종의 물체에 대해 어떤 물체든
용량과 val의 비율은 항상 일정하고 1:1의 관계이다.
1:2, 1:3 또는 2:3 따위가 아니라 dp[j-a]+b에서 a=b=val[i], a:b==1:1,
그래서 보증합니다. 만약에 용량이 i인 상태가 도달할 수 있다면 마지막 dp[i]는 반드시 ==i입니다."
(a==b 때문에);
그래서 이 상태로 방정식을 옮길 필요가 있어요. 마수를 발로 베는 칼은 돼지에게 눌렸어요.
이렇게 많아
2013-03-14
*/
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
const int N=111;
const int M=100111;
int n,m;
int val[N],c[N],flag[M];
int main()
{
int i,l;
int k,t,temp;
while(scanf("%d%d",&n,&m),n||m)
{
for(i=0;i<n;i++) scanf("%d",&val[i]);
for(i=0;i<n;i++) scanf("%d",&c[i]);
memset(flag,0,sizeof(flag));
flag[0]=1;
for(i=0;i<n;i++)
{
//
if(c[i]*val[i]>=m)
{
for(l=val[i];l<=m;l++)
flag[l]=flag[l] || flag[l-val[i]];
}
//0-1
else
{
k=1;
t=c[i];
while(k<t)
{
temp=k*val[i];
for(l=m;l>=temp;l--)
flag[l]=flag[l] || flag[l-temp];
t-=k;
k<<=1;
}
if(t)
{
temp=t*val[i];
for(l=m;l>=temp;l--)
flag[l]=flag[l] || flag[l-temp];
}
}
}
int ans=0;
for(i=1;i<=m;i++) if(flag[i]) ans++;
printf("%d
",ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
