我是靠谱客的博主 彩色花生,这篇文章主要介绍算法练习题——0 1背包问题,现在分享给大家,希望可以做个参考。

时间限制:  2  S         内存限制:  128  MB

题目描述:

给你一个固定容量的背包v,和n个物品。每个物品有它的体积和价值,每个物品只能拿1个,在总物品的体积不超过背包容量的前提下可以获得的最大价值。

输入:

第一行输入两个int型整数v和n,表示背包的容量和给出的物品数。(v<=1000,n<=100)然后给出n个物品,vi和mi表示物品的体积和价值。(1<=vi<=mi<=1000)

输出:

输出一个整数表示所能得到的最大价值并换行。

样例输入:

100 5 77 92 22 22 29 87 50 46 99 90

样例输出:

133

Language: C++

 #include <iostream>  

#include<fstream>  
#include<algorithm>  
#include<vector>  


typedef struct item  
{  
    int vi;  
    int mi;  
}item;  
using namespace std;


int max(int x,int y){
int temp = 0;
if(x>y) temp=x;
else temp=y;
return temp;


}  
int main()  
{  
    int v;  
    int n;    
    cin>>v>>n;     
    vector<vector<int> > k(v+1,vector<int>(n+1));  
    item items[100];  
    for(int i=0;i<n;i++){  
         cin>>items[i].vi;  
         cin>>items[i].mi;  
    }       
    for(int w=0;w<=v;w++)  
    {  
        for(int j=0;j<=n;j++)  
        {  
            k[w][j]=0;      
        }  
      
    }  
    for(int w1 = 1;w1<=v;w1++)  
    {  
        for(int j=1;j<=n;j++)  
        {  
            if(items[j-1].vi>w1)        
            {  
                k[w1][j]=k[w1][j-1];  
            }  
            else      
            {  
                k[w1][j]=max(k[w1][j-1],(k[w1-items[j-1].vi][j-1]+items[j-1].mi));  
            }  
              
        }  
          
    }    
    cout<<k[v][n]<<endl;   
return 0;
}  



最后

以上就是彩色花生最近收集整理的关于算法练习题——0 1背包问题的全部内容,更多相关算法练习题——0内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(61)

评论列表共有 0 条评论

立即
投稿
返回
顶部