0-1背包-白红宇

0-1背包

阅读量：3960 次

发布时间：2019-05-24

本文共 905 字，大约阅读时间需要 3 分钟。

给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:

共有n+1行输入：第一行为n值和c值，表示n件物品和背包容量c；接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:

输出装入背包中物品的最大总价值。

输入样例:

在这里给出一组输入。例如：

5 10

2 6

2 3

6 5

5 4

4 6

输出样例:

在这里给出相应的输出。例如：

#include
   
    #include
    
     #include
     
      using namespace std;int dp[1001][1001]={
   0};int main(){
       int n,c;    memset(dp,0,sizeof(dp));    cin>>n;    cin>>c;    int *v=new int[n+1];    int *w=new int[n+1];    for(int i=1;i<=n;i++)    cin>>w[i]>>v[i];    int maxnum=0;    for(int i=1;i<=n;i++)        for(int j=0;j<=c;j++)        {
               dp[i][j] = dp[i-1][j];            if(j>=w[i])            {
                   dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);                if(dp[i][j]>maxnum)maxnum = dp[i][j];            }        }    cout<
      
       <

转载地址：http://pyezi.baihongyu.com/

你可能感兴趣的文章