DP(完全背包)

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


Solution

第一层循环是从第一个物品到第n个物品的循环

第二层循环是先装第一种物品直到装满,然后分别对加入该物品后的体积和价值保留,然后再考虑从包中拿出某个第一种物品,加入第二种物品,直到装满,且价值最大。依次循环直到第n种物品,整个包装满且价值最大。

#include<cstdio>
#include<algorithm>
using namespace std;
int w[1000],c[1000],f[300010];
int V,n;
int main(){
scanf("%d%d",&V,&n);
for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&c[i]);}
for(int i=1;i<=n;i++)
for(int j=w[i];j<=V;j++)f[j]=max(f[j],f[j-w[i]]+c[i]);
printf("%d",f[V]);
return 0;
}