s*w
发帖数: 729 | 1 codeeval.com 上的一个题
给n个东西，每个东西有重量和价值，要求在重量小于给定值的时候，尽量价值大
在重量是浮点数的情况下，怎么做 bottomup 的 dp table?
我现在的解是 recursion, 而且没 memorization, 因为不知道怎么存这个 table.
帖下代码，请指教一下
#include
#include
#include
#include
#include
#include
using namespace std;
class Solution {
int weightLimit;
int n;
vector weights;
vector costs;
public:
Solution(const string &line) {
istringstream iss(line);
iss >> weightLimit;
int ind,cost;
double weight;
do {
iss.ignore(256,'(');
iss >> ind;
iss.ignore(256,',');
iss >> weight;
iss.ignore(256,'$');
iss >> cost;
iss.ignore(256,')');
if(iss.good()) {
weights.push_back(weight);
costs.push_back(cost);
}
} while(iss.good());
n = weights.size();
}
vector run2(double wlimit, vector ind) {
vector bestInd;
int bestValue = 0;
for(int i=0;i
vector tInd;
int tValue = 0;
double wlimit2 = wlimit - weights[ind[i]];
if(wlimit2 > 0) {
// update tValue and tInd due to chosing a valid ind[i]
tValue += costs[ind[i]];
tInd.push_back(ind[i]);
// solve subproblem
vector ind2(ind);
ind2.erase(ind2.begin()+i);
vector ret2 = run2(wlimit2,ind2);
if(!ret2.empty())
// update tValue and tInd due to valid subproblem solution
for(auto j : ret2) {
tValue += costs[j];
tInd.push_back(j);
}
}
// update best if necessary
if(tValue>bestValue) {
bestValue = tValue;
bestInd = tInd;
}
}
return bestInd;
}
void run() {
vector ind;
for(int i=0;i
ind.push_back(i);
vector ret = run2(weightLimit,ind);
if(ret.empty())
cout << "-" << endl;
else if(ret.size()==1)
cout << ret[0]+1 << endl;
else {
for(int i=0;i
cout << ret[i]+1 << ",";
cout << ret[ret.size()-1]+1 << endl;
}
}
};
int main(int argc,char* argv[]) {
if(argc<2)
throw invalid_argument("need 1 parameter");
ifstream ifs(argv[1]);
string line;
while(getline(ifs,line)) {
Solution sol(line);
sol.run();
}
} | b**********5
发帖数: 7881 | | a********m
发帖数: 15480 | 3 浮点的话是麻烦，毕竟是伪多项式。不过一般价格位数有限，弄成整数也还能做。
【在 s*w 的大作中提到】
: codeeval.com 上的一个题
: 给n个东西，每个东西有重量和价值，要求在重量小于给定值的时候，尽量价值大
: 在重量是浮点数的情况下，怎么做 bottomup 的 dp table?
: 我现在的解是 recursion, 而且没 memorization, 因为不知道怎么存这个 table.
: 帖下代码，请指教一下
: #include
: #include
: #include
: #include
: #include
|
|
