포켓 2755

poj 2755 신기한 주머니(dp) 총 시간 제한: 10000ms 메모리 제한: 65536kB
신기한 주머니가 있는데, 총 부피는 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;
}