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

一、01背包’

例题：高数Umaru系列（9）——哈士奇

由于高数巨养的喵星人太傲娇了，要天天吃新鲜猫粮而且还经常欺负高数巨，所以高数巨决定买几条哈士奇尝尝鲜。这天高数巨来到了二手狗市场买哈士奇，高数巨看完了所有的哈士奇，记下了每条哈士奇的价格，并根据对它们的好感程度给它们每只都赋予了一个萌值。高数现在手里有X元，她想通过购买若干条哈士奇来获得尽可能多的萌值。现在给定高数巨手里的钱X以及N条哈士奇的价格和萌值，求高数巨最多可获得多少萌值

Input

多组输入。 对于每组输入，第一行有两个整数N，X（1 < = N < = 100，1 < = X < = 1000），分别表示哈士奇的数量和高数巨的钱数 接下来的N行每行有两个整数Pi，Mi（1 < = Pi,Mi < = 100），分别表示第i条哈士奇的价格和萌值

Output

对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行

Sample Input

2 100 50 20 60 40 3 100 20 55 20 35 90 95 1 10 20 50

Sample Output

40 95 0

#include
   
    typedef struct node{
       int p;    int m;} NODE;int max(int a,int b){
       return  a>b?a:b;}int main(){
       int i,j,n,mm;    NODE k[200];    while(scanf("%d %d",&n,&mm)!=EOF)    {
           int f[20000]={
   0};		//要先置零；        for(i=0; i
    
     =1; j--)	//遍历背包容量；01背包是从大到小遍历容量；            {
                   if(j>=k[i].p)                {
                       f[j]=max(f[j],f[j-k[i].p]+k[i].m);                }            }        }        printf("%d\n",f[mm]);    }    return 0;}
    
   

二、完全背包

例题：小P寻宝记——好基友一起走

话说，上次小P到伊利哇呀国旅行得到了一批宝藏。他是相当开心啊，回来就告诉了他的好基友小鑫，于是他们又结伴去伊利哇呀国寻宝。

这次小P的寻宝之路可没有那么的轻松，他们走到了一个森林，小鑫一不小心被触发了机关，被困在了一个大笼子里面，笼子旁边上有一道题目和一个密码锁，上面说只要解出此题输入密码即可救出被困人。小鑫不是很聪明，所以他做不出来，他知道小P很笨，更解不出来。所以他就让小P独自回去，不用管他。但是小P重情重义不会抛弃他离去。他说：“不，好基友一起走！”。于是就感动了上帝，上帝特派你来替他们解决问题。聪明的你要加油了啊！ 题目描述：给你n种物品和一个体积为v的包包。每种物品有无数种，体积是vi价值是wi。求出包包v所能装的最大价值的东西。

Input

多组输入。第一行有两个正整数n(0<n<=10000), v(0<v<= 10000)。接下来两行每行有n个数字。第一行表示每种物品的价值wi(0<wi<100)，第二行表示每种物品的体积vi(0<vi<100)。

Output

输出最多可以得到的价值。输出结果救出小鑫。

Sample Input

5 20 1 2 3 4 5 2 6 3 5 4

Sample Output

25

#include
   
      #include
    
       int dp[10100],wi[10100],vi[10100];  int main()  {
         int n,v,i,j;      while(scanf("%d %d",&n,&v)!=EOF)      {
             memset(dp,0,sizeof(dp));          for(i=1;i<=n;i++)              scanf("%d",&wi[i]);          for(i=1;i<=n;i++)              scanf("%d",&vi[i]);          for(i=1;i<=n;i++)          {
                 for(j=vi[i];j<=v;j++)              {
                         dp[j]=dp[j]>dp[j-vi[i]]+wi[i]?dp[j]:dp[j-vi[i]]+wi[i];              }          }          printf("%d\n",dp[v]);      }      return 0;  }
    
   

转载地址：https://blog.csdn.net/qq_43419016/article/details/89971789 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！