01背包问题

2. 01背包问题 - AcWing题库（悟了一个下午）用表格理解最佳

朴素型：

#include 
#include 
#include 
#include 
#include 

int main()
{
    int N,V,i,j;
    scanf("%d",&N);
    scanf("%d",&V);
    int v[1001];
    int w[1001];
    v[0]=0;w[0]=0;
    for(i=1;i<=N;i++)
    {
        scanf("%d",&v[i]);
        scanf("%d",&w[i]);
    }
    int arr[N+1][V+1];
    for(i=0;i<=N;i++)
    {
        for(j=0;j<=V;j++)
        {
            if(i==0||j==0)
            {
                arr[i][j]=0;
            }
            else
            {
                if(v[i]>j)
                {
                    arr[i][j]=arr[i-1][j];
                }
                else
                {
                    if(arr[i-1][j]>arr[i-1][j-v[i]]+w[i])
                    {
                        arr[i][j]=arr[i-1][j];
                    }
                    else
                    {
                        arr[i][j]=arr[i-1][j-v[i]]+w[i];
                    }
                }
            }
        }
    }
    printf("%d",arr[N][V]);
    return 0;
} 

优化型：

#include 
#include 
#include 
#include 
#include 
int main()
{
    int N,V,i,j;
    scanf("%d",&N);
    scanf("%d",&V);
    int v[1001];
    int w[1001];
    v[0]=0;w[0]=0;
    for(i=1;i<=N;i++)
    {
        scanf("%d",&v[i]);
        scanf("%d",&w[i]);
    }
    int arr[V+1];
    for(i=0;i<=N;i++)
    {
        for(j=V;j>=0;j--)
        {
            if(i==0||j==0)
            {
                arr[j]=0;
            }
            else
            {
                if(j>=v[i]&&arr[j]