NO IMAGE

網址連結

思路

  • 之前想的是如果使用揹包問題求解,則問題的空間複雜度很大,這個只包含1和2兩種體積的方法,因此可以適當簡化。
  • 我看了別人提交的答案,直接使用dp,提交了也可以AC。。

程式碼

#include <cstdlib>
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <stdio.h>
#include <numeric>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned char uchar;
const int MOD = 1e9   7;
int dirs[8][2] = { -1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1 };
//#define debug_
int n; long long v;
vector<int> volum;
vector<int> value;
// 01揹包問題求解
void func()
{
vector<vector<int>> dp( n 1, vector<int>(v 1, 0) );
int lhs, rhs;
for (auto i = 1; i < dp.size();   i)
{
for (auto j = 1; j < dp[i].size();   j)
{
lhs = 0;
rhs = 0;
lhs = dp[i - 1][j];
if (j - volum[i - 1] >= 0)
{
rhs = dp[i - 1][j - volum[i - 1]]   value[i - 1];
}
dp[i][j] = max(lhs, rhs);
}
}
cout << dp[n][v] << endl;
vector<int> printvec;
if (dp[n][v] == 0)
{
cout << "No" << endl;
}
else
{
int i = n, j = v;
while (i)
{
if (dp[i][j] != dp[i - 1][j])
{
printvec.push_back(i);
j = j - volum[i - 1];
}
i--; // 等於的話,表明這個狀態時,沒有candy
}
for (int j_ = printvec.size() - 1; j_ >= 0; j_--)
{
cout << printvec[j_] << ' ';
}
cout << endl;
}
}
int main()
{
#ifdef debug_
n = 3;
v = 2;
volum.push_back(1);
volum.push_back(1);
volum.push_back(1);
value.push_back(2);
value.push_back(2);
value.push_back(3);
func();
#else
while (cin >> n)
{
cin >> v;
long long max_volume(0);
volum.clear();
value.clear();
volum.resize(n);
value.resize(n);
for (auto i = 0; i < n;   i)
{
cin >> volum[i];
cin >> value[i];
max_volume  = volum[i];
}
if (max_volume <= v) //所有的加起來都沒有到達總和,直接輸出所有的
{
cout << accumulate(value.begin(), value.end(), 0) << endl;
for (auto i = 1; i < n   1;   i)
{
cout << i << " ";
}
cout << endl;
}
else
{
func();
}
}
#endif
system("pause");
return 0;
}