1013. 無限背包
Description
你現(xiàn)在有一個(gè)體積為V的大袋子糙捺，有N種物品诫咱，假設(shè)每種物品的數(shù)量有無限多個(gè)，而且第i種物品的體積是c[i],價(jià)值是w[i],請選擇一些物品放入袋中洪灯，使袋中物品的價(jià)值總和最大坎缭。
注意每種物品的數(shù)量是無限多的；對于放入袋中的同種物品數(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;
}
