nyoj106 背包問題

nyoj106 背包問題
背包問題

時間限制： 3000 ms | 記憶體限制： 65535 KB 難度： 3

描述

現在有很多物品（它們是可以分割的），我們知道它們每個物品的機關重量的價值v和重量w（1<=v,w<=10）；如果給你一個背包它能容納的重量為m（10<=m<=20）,你所要做的就是把物品裝到背包裡，使背包裡的物品的價值總和最大。

輸入

第一行輸入一個正整數n（1<=n<=5）,表示有n組測試資料；

随後有n測試資料，每組測試資料的第一行有兩個正整數s，m（1<=s<=10）;s表示有s個物品。接下來的s行每行有兩個正整數v，w。

輸出

輸出每組測試資料中背包内的物品的價值和，每次輸出占一行。

樣例輸入

樣例輸出

應用貪心算法。這個題目已經告訴你機關價值了，是以不需要考慮計算機關價值最高的，從高到低的選擇了。我們現在所需要做的就是對機關價值進行排序，然後從高到底取物品，直到重量達到題目中告訴的背包的W。

sort排序，結構體或者二維數組進行儲存資料。最後執行計算價值和，不過值得留意就是那個對結構體資料的交換，不用單獨定義一個變量，而是用結構體中最後一個多餘的進行儲存，這是一個小妙招！貪心算法，求局部的最優解，需要看清的是每個（物品的機關重量的價值v和重量w）

法一：

2 #include<stdio.h>
 3 struct wupin
 4 {
 5     int a;
 6     int b;
 7 }wu[11];
 8 int main()
 9 {   
10     int i,j,l,n,s,m,x,q;
11     scanf("%d",&n);
12     while(n--)
13     {
14         scanf("%d%d",&s,&m);
15         for(i=0;i<s;i++)
16             scanf("%d%d",&wu[i].a,&wu[i].b);
17         for(i=0;i<s-1;i++)
18         {
19                 for(j=0;j<s-i-1;j++)
20                 if(wu[j].a>wu[j+1].a)
21                 {
22                     wu[10]=wu[j];
23                     wu[j]=wu[j+1];
24                     wu[j+1]=wu[10];
25                 }//此處就是進行結構體交換的地方，利用最後一個多餘的結構體儲存。
26         }
27         if(wu[s-1].b>=m)
28             printf("%d\n",m*wu[s-1].a);
29         else
30         {
31             int sum=0,k=0;
32             for(i=s-1;i>=0;i--)
33             {
34                 sum+=wu[i].b;k+=wu[i].a*wu[i].b;//進行計算。
35                 if(m<=sum)
36                 {k-=(sum-m)*wu[i].a;break;}              
37             }
38             printf("%d\n",k);
39         }
40     }return 0;
41 }

法二：
1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 struct bb//**定義一個背包的結構體**//
 5 {
 6     int jz;//**價值**//
 7     int zl;//**重量**//
 8 }w[100];
 9 bool comp(bb x,bb y)//**将價值高的排前**//
10 {
11      if(x.jz>y.jz) return true;
12      return false; 
13 }
14 int main()
15 {
16     int s,n,m,i,j,jzsum,zlsum,sum;
17     scanf("%d",&s);
18     while(s--)
19     {
20         jzsum=0;zlsum=0;//**價值的總和****重量的總和**//
21         scanf("%d %d",&n,&m);
22         for(i=0;i<n;i++)
23         {
24             scanf("%d %d",&w[i].jz,&w[i].zl);
25         }
26         sort(w,w+n,comp);
27         for(i=0;i<n;i++)
28         {
29             zlsum=zlsum+w[i].zl;
30             if(zlsum<=m)//**如果背包的容量大于等于全部物品的重量和**//
31             {
32                 jzsum=jzsum+w[i].jz*w[i].zl;
33             }
34             if(zlsum>m)//**如果背包的容量小于全部物品的重量和**//
35             {
36                 sum=m-(zlsum-w[i].zl);//**把多出物品的重量減去**//
37                 jzsum=jzsum+sum*w[i].jz;
38                 break;
39             }
40         }
41         printf("%d\n",jzsum);
42     }
43     return 0;
44 }

背包問題其實并不難，就是求局部最優解，明了題目的目的就好辦了，是個很有特點的算法

nyoj106 背包問題

nyoj106 背包問題