1013. 無限背包

Description

你現(xiàn)在有一個(gè)體積為V的大袋子，有N種物品，假設(shè)每種物品的數(shù)量有無限多個(gè)，而且第i種物品的體積是c[i],價(jià)值是w[i],請(qǐng)選擇一些物品放入袋中，使袋中物品的價(jià)值總和最大。

注意每種物品的數(shù)量是無限多的；對(duì)于放入袋中的同種物品數(shù)量沒有限制。

Input Format

第一行包含兩個(gè)正整數(shù)V和N，分別代表袋子的體積和物品的種類數(shù)。

以下N行分別由2個(gè)正整數(shù)組成，代表每種物品的體積和價(jià)值。

V≤10000,N≤1000。

保證操作可在C++ int范圍內(nèi)完成。

Output Format

輸出一個(gè)整數(shù)，表示最大的價(jià)值總和

Sample Input

5 3
2 3
3 2
4 1

Sample Output

6

分析

這是一個(gè)典型的動(dòng)態(tài)規(guī)劃問題，其關(guān)鍵也是記錄中間結(jié)果。

#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;
}