Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int max(int a, int b)
- {
- return (a > b) ? a : b;
- }
- int main()
- {
- int N, W, V;
- int c[100] = { 0 };
- int w[100] = { 0 };
- int v[100] = { 0 };
- int table[101][101] = { 0 };
- int ans[101] = { 0 };
- cin >> N; //輸入物品個數
- cin >> W; //輸入背包所能承載之重量
- cin >> V; //輸入背包所能承載之體積
- for (int i = 0; i < N; i++)
- {
- cin >> c[i]; //輸入各個物品的價值
- }
- for (int i = 0; i < N; i++)
- {
- cin >> w[i]; //輸入各個物品的重量
- }
- for (int i = 0; i < N; i++)
- {
- cin >> v[i];
- }
- int i, j = 1, weight, volume, used[100] = { 0 };
- for (i = 0; i <= N; i++)
- {
- for (weight = 0;weight <= W;weight++)
- {
- for (volume = 0; volume <= V; volume++)
- {
- if (i == 0 || weight == 0 || volume == 0)
- {
- table[weight][volume] = 0;
- }
- else if (w[i - 1] <= weight && v[i - 1] <= volume)
- {
- table[weight][volume] = max(c[i - 1] + table[weight - w[i - 1]][volume - v[i - 1]], table[weight][volume]);
- }
- }
- }
- }
- cout << table[W][V] << endl;;
- int numbers = 0, temp = 0;
- weight = W;
- for (volume = V; volume >= 1; volume--)
- {
- if (table[weight][volume] == table[weight][volume - 1])
- continue;
- else if (table[weight][volume] > table[weight][volume - 1])
- {
- temp = table[weight][volume] - table[weight - 1][volume - 1];
- for (int i = N - 1; i >= 0; i--)
- {
- if (c[i] == temp)
- ans[i + 1] = 1;
- }
- weight--;
- }
- }
- for (int i = 1; i <= N; i++)
- {
- if (ans[i] == 1)
- numbers++;
- }
- cout << numbers << endl;
- cout << "(";
- weight = W;
- for (int i = 1; i <= N; i++)
- {
- if (ans[i] == 1)
- {
- cout << i;
- weight -= w[i - 1];
- for (int j = i+1; j <= N; j++)
- {
- if (ans[j] == 0)
- continue;
- else if (ans[j] != 0)
- {
- cout << ",";
- break;
- }
- }
- }
- }
- cout << ")";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement