-->
当前位置:首页 > 题库 > 正文内容

7-15 完全背包 (10 分)

Luz3年前 (2021-03-31)题库1294
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;
}


发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。