北工大アルゴリズム作業2動的計画01リュックサック問題
2368 ワード
次の文章を参考にして、考え方がはっきりしています.
https://blog.csdn.net/u010293698/article/details/48979623
https://blog.csdn.net/sinat_22991367/article/details/51861373
n種類の物品と1つのリュックサックが与えられ、物品iの重量はwiであり、その価値はviであり、リュックサックの容量はCである.リュックサックの問題は、リュックサックに入ったものをどのように選択して、リュックサックに入ったものの総価値を最大にするかということです.リュックサックを入れるものを選ぶ場合、リュックサックを入れるか入れないかの2つの選択肢しかない.すなわち、荷物iを何度もリュックサックに入れることができず、荷物iの一部だけを入れることができない場合、0/1リュックサック問題と呼ぶ.
https://blog.csdn.net/u010293698/article/details/48979623
https://blog.csdn.net/sinat_22991367/article/details/51861373
n種類の物品と1つのリュックサックが与えられ、物品iの重量はwiであり、その価値はviであり、リュックサックの容量はCである.リュックサックの問題は、リュックサックに入ったものをどのように選択して、リュックサックに入ったものの総価値を最大にするかということです.リュックサックを入れるものを選ぶ場合、リュックサックを入れるか入れないかの2つの選択肢しかない.すなわち、荷物iを何度もリュックサックに入れることができず、荷物iの一部だけを入れることができない場合、0/1リュックサック問題と呼ぶ.
// 2 01 .cpp : 。
//
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
#include
#define MAX 100
using std::ifstream;
using std::vector;
using std::endl;
using std::cout;
using std::max;
using std::make_shared;
using std::shared_ptr;
using std::string;
class Object
{
public:
int weight;
int value;
};
//
int main()
{
for (int i = 0; i < 5; i++)
{
cout << " "< v;
while (infile >> temp)
{
v.push_back(temp);
}
shared_ptr> oj = make_shared>();
int f[MAX][MAX];//
int num, C;//
int count = 0;
Object oo;
for (auto x = v.cbegin(); x != v.cend(); x++)
{
if (x == v.cend() - 1)
{
C = *x;
cout << " :" << C << endl;
break;
}
if (count == 0) // value weight
{
oo.value = *x;
cout << " :" << oo.value << " ";
count = 1;
}
else
{
oo.weight = *x;
cout << " :" << oo.weight << endl;
count = 0;
oj->push_back(oo);
}
//oj->push_back(oo);
}
num = oj->size();
//cout << num << endl;
for (int i = 0; i <= num; i++)
{
for (int j = 0; j <= C; j++)
{
f[i][j] = 0;
}
}
for (int i = 1; i <= num; i++)
{
for (int j = oj->at(i - 1).weight; j <= C; j++)
{
f[i][j] = max(f[i - 1][j], f[i - 1][j - oj->at(i - 1).weight] + oj->at(i - 1).value);
//cout << "f["<