7-15 完全背包 (10 分)
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
输入格式:
第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
输出格式:
仅一行，一个数，表示最大总价值。
输入样例:
10 4
2 1
3 3
4 5
7 9
输出样例:
max=12
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
//Ans1:
#include<iostream>
#include<vector>
using namespace std;
int fun(int n,int v,vector<int> weight,vector<int> price,vector<int> res){
for(int i=1;i<=n;++i){
for(int j=weight[i];j<=v;++j){
res[j] = max(res[j],res[j-weight[i]]+price[i]);
}
}
return res[v];
}
int main(){
int n,v;
cin>>v>>n;
vector<int> weight(n+1,0);
vector<int> price(n+1,0);
vector<int> res(v+1);
for(int i=1;i<=n;++i){
cin>>weight[i]>>price[i];
}
int ans = fun(n,v,weight,price,res);
cout<<"max="<<ans<<endl;
return 0;
}//Ans2: 动态规划
#include <iostream>
using namespace std;
int f[1000];
int main()
{
int n,m;
cin>>m>>n;
for(int i=0;i<n;i++)
{
int v,c;
cin>>v>>c;
for(int j=v;j<=m;j++){
f[j]=max(f[j],f[j-v]+c);
}
}
cout<<"max="<<f[m]<<endl;
return 0;
}