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