完全背包
时间限制： 3000 ms |内存限制： 65535 KB
难度： 4
说明
直截了当地说，完整背包定义了n种类型的项目和容量为v的背包，每个项目都有无限的项目。 第I项的体积是c，价值是w。 求出哪个物品放入背包，这些物品的体积总和不会超过背包的容量，且价值总和最大。 本问题的要求是求出背包刚好装满时，最大价值的总和是多少。 背包装不牢时，输出NO
输入
第1行： n表示测试数据(N7 )的组有几个。
其次，每个测试数据的第一行有两个整数m、v。 m表示物品种类的数量，v表示背包的总容量。 (0m=2000，0v=50000 )
以下m行每行包含两个整数c，其中w表示每个物品的重量和价值(0. c 100000，0w 100000 )
输出功率
对应各组测试数据输出结果(如果背包正好装满，则输出背包装满时背包内物品最大价值的总和。 如果不能将背包装得很紧，则输出NO )
样本输入
2
1 5
2 2
2 5
2 2
5 1
样本输出
否
1
问题： http://www.Sina.com/http://www.Sina.com /分别有n个wi、vi的重量和价值，从中选择总重量不超过w的，在所有筛选方案中求出价值总和的最大值
有与01背包的区别：个重量和价值分别为wi、vi的物品，从这些物品中选择总重量在w以下的物品，在所有分拣方案中求出价值总和的最大值，对每个物品选择多个，将完整背包改为0.1背包
DP[I][j]=max(DP[I-1][j-k*w[I] ) k * v [ I ] (0=k * w [ I ] (w ) ) ) () ) ) )
一维数组DP [ I ]=转换为max (DP [ j-k * w [ I ] ) k*v[I] ) *
# include bits/stdc.husingnamespacestd； 常数int maxn=100000 5； 结构rec { int c； int w； }vis[maxn]； int n，m，v； 龙龙Dp [ maxn ]； void DP () for ) intI=1； i=m； I ) for(intj=vis[I].c； j=v； j({DP[j]=max(DP[j]，dp[j-vis[i].c] vis[i].w )； }if(DP[v]0) cout'NO'endl； else coutdp[v]endl； (}int main ) ) { cinn； wile(n-- ) memset ) DP，-10000，sizeof ) ) DP )； //01背包初始化为0，其中初始化相对较大的负dp[0]=0； cinmv； for(intI=0； im； I ) { cinvis[i].cvis[i].w； (DP )； }返回0； }