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