01背包 无限背包

第一行两个整数V和n。
接下来n行，每行两个整数体积和价值。1≤N≤1000,1≤V≤20000。
每件物品的体积和价值范围在[1,500]。

输出背包最多能装的物品价值。

// niuke.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>

int maxVal(int a, int b);

int main()
{
    int V = 0;
    int N = 0;
    int size[1010] = {0};
    int val[1010] = {0};
    int result[20010] = {0};
    
    scanf("%d %d", &V, &N);
    
    for(int i = 0; i < N; ++i)
    {
        scanf("%d %d",&size[i],&val[i]);
    }
    for(int i = 0; i < N; ++i)//01背包
    {
        //无限背包  for(int j=size[i]; j <= V; j++)
        for(int j = V; j >= size[i]; --j)
        {
            result[j] = maxVal(result[j], result[j - size[i]] + val[i]);
        }
    }
    printf("%d",result[V]);
    return 0;
}
 
int maxVal(int a, int b)
{
    return a >= b ? a : b;
}