HDOJ 2602 Bone Collector(0-1 백팩)

1898 단어
제목 링크:...
신입 첫 번째 0-1 가방 문제
동적 방정식: dp[j]=max(dp[j], dp[j-V[i]]+W[i])j를 용량으로 하고 마지막 dp[v]는 답을 구한다.
code:
#include <stdio.h>
#include <string.h>
int main()
{
    int i = 0, j = 0, t = 0, n = 0, v = 0;
    int W[1002], V[1002], dp[1002];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n, &v);
        for(i = 0; i<n; i++)
            scanf("%d",&W[i]);
        for(i = 0; i<n; i++)
            scanf("%d",&V[i]);
        memset(dp, 0, sizeof(dp));
        for(i = 0; i<n; i++)
        {
            for(j = v; j>=V[i]; j--)//j         
            {
                dp[j] = dp[j]<(dp[j-V[i]]+W[i])? (dp[j-V[i]]+W[i]):dp[j];
            }
        }
        printf("%d
",dp[v]); } return 0; }

2차원수 그룹 동적 방정식: dp[i][j]=max(dp[i-1][j], dp[i-1][j-V[i]]]+W[i]) dp[i][j]: 제 i 물품 용량이 j일 때 있는 가치
code:
#include <stdio.h>
#include <string.h>
int dp[1002][1002];
int main()
{
    int i = 0, j = 0, t = 0, n = 0, v = 0;
    int W[1002], V[1002];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n, &v);
        for(i = 0; i<n; i++)
            scanf("%d",&W[i]);
        for(i = 0; i<n; i++)
            scanf("%d",&V[i]);
        memset(dp, 0, sizeof(dp));
        for(i = 0; i<V[0]; i++)
            dp[0][i] = 0;
        for(i = V[0]; i<=v; i++)
            dp[0][i] = W[0];
        for(i = 1; i<n; i++)
        {
            for(j = 0; j<V[i]; j++)
                dp[i][j] = dp[i-1][j];
            for(j = V[i]; j<=v; j++)
                dp[i][j] = dp[i-1][j]>dp[i-1][j-V[i]]+W[i]? dp[i-1][j]:dp[i-1][j-V[i]]+W[i];
        }
        printf("%d
",dp[n-1][v]); } return 0; }

좋은 웹페이지 즐겨찾기