0/1 背包問題
背包問題的不可分割版，參考上課投影片，實做一個 0/1 背包問題演算法。
Input
第一行為測資組數 N，接著有 N 組測資，每組三行。
每組的第一行為背包的最大負重、每組的第二行為物品的重量、每組的第三行為物品的價值，每組皆只有五個物品。
Output
請輸出 N 行，可拿取的最大物品總價。
範例輸入：
3
10
3 1 4 2 5
7 10 9 4 8
17
7 4 8 7 12
3 2 1 4 7
38
12 7 32 5 21
8 5 19 8 14
範例輸出：
30
9
30
/*----- ----- ----- -----*/ //1-01背包 //Made by 105502555 Teemo Hsu(Synasaivaltos) //Date: 2018/05/14 /*----- ----- ----- -----*/ #include <iostream> #include <vector> using namespace std; const int COUNT=5; typedef struct Item { int weight; int value; }Item; int main(void) { int n; cin >> n; vector<int> ans; while(--n>=0) { int weight; cin >> weight; Item item[COUNT+1]; item[0].weight=0,item[0].value=0; for(int i=1;i<=COUNT;cin>>item[i].weight,i++); for(int i=1;i<=COUNT;cin>>item[i].value,i++); for(int i=1;i<=COUNT;i++) { for(int j=i+1;j<=COUNT;j++) { if(item[i].value<item[j].value) { swap(item[i].weight,item[j].weight); swap(item[i].value,item[j].value); } } } int select[COUNT+1][weight+1]; for(int i=1;i<=weight;select[0][i]=0,i++); for(int i=1;i<=COUNT;i++) { select[i][0]=0; for(int j=1;j<=weight;j++) { if(item[i].weight<=j) { if((item[i].value+select[i-1][j-item[i].weight])>select[i-1][j]) select[i][j]=item[i].value+select[i-1][j-item[i].weight]; else select[i][j]=select[i-1][j]; } else select[i][j]=select[i-1][j]; } } ans.push_back(select[COUNT][weight]); } for(int i=0;i<ans.size();cout<<ans.at(i)<<endl,i++); return 0; } |
