上交OJ-1013. 无限背包

1013. 无限背包

---

Description

你现在有一个体积为V的大袋子，有N种物品，假设每种物品的数量有无限多个，而且第i种物品的体积是c[i],价值是w[i],请选择一些物品放入袋中，使袋中物品的价值总和最大。

注意每种物品的数量是无限多的；对于放入袋中的同种物品数量没有限制。

Input Format

第一行包含两个正整数V和N，分别代表袋子的体积和物品的种类数。

以下N行分别由2个正整数组成，代表每种物品的体积和价值。

V≤10000,N≤1000。

保证操作可在C++ int范围内完成。

Output Format

输出一个整数，表示最大的价值总和

Sample Input

5 3
2 3
3 2
4 1

Sample Output

6

分析

这是一个典型的动态规划问题，其关键也是记录中间结果。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
    int V,N;
    int space[1001],value[1001];
    int tmp_V[10001];
    int i,j;
    
    memset(tmp_V, 0, sizeof(tmp_V));
    
    cin>>V>>N;
    for(i=1; i<=N; i++)
        cin>>space[i]>>value[i];
    
    for(i=1; i<=V; i++) {
        for(j=1; j<=N; j++) {
            if(i >= space[j])
                tmp_V[i]=max(tmp_V[i], tmp_V[i-space[j]]+value[j]);
        }
    }
    
    cout<<tmp_V[V]<<endl;
    
    return 0;
}