脚本宝典收集整理的这篇文章主要介绍了1268:【例9.12】完全背包问题,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
设有nn种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为MM,今从nn种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于MM,而价值的和为最大。
第一行:两个整数,MM(背包容量,M≤200M≤200)和NN(物品数量,N≤30N≤30);
第2..N+12..N+1行:每行二个整数Wi,CiWi,Ci,表示每个物品的重量和价值。
仅一行,一个数,表示最大总价值。
10 4 2 1 3 3 4 5 7 9
max=12代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int v[55],w[55],f[205];
int main()
{
int N,V;
cin>>V>>N;
for(int i=1;i<=N;i++)cin>>v[i]>>w[i];
for(int i=1;i<=N;i++)
for(int j=v[i];j<=V;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<"max="<<f[V]<<endl;
}
|
以上是脚本宝典为你收集整理的1268:【例9.12】完全背包问题全部内容,希望文章能够帮你解决1268:【例9.12】完全背包问题所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。