プログラマ専用SNS ミクプラ

コード:

#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define limit 121         // ナップサックの重量制限値
#define n 10             // 品物の種類

struct body 
{
    string name;     // 品名
    int size;       // 重さ 
    int price;     // 価格 
};

int main(void)
{
     // データの格納
     struct body a[10];
     a[0].name="1"; a[0].size=20; a[0].price=61;
     a[1].name="2"; a[1].size=31; a[1].price=89;
     a[2].name="3"; a[2].size=15; a[2].price=32;
     a[3].name="4"; a[3].size=41; a[3].price=47;
     a[4].name="5"; a[4].size=16; a[4].price=18;
	 a[5].name="6"; a[5].size=39; a[5].price=42;
     a[6].name="7"; a[6].size=13; a[6].price=12;
     a[7].name="8"; a[7].size=68; a[7].price=45;
     a[8].name="9"; a[8].size=15; a[8].price=5;
     a[9].name="10"; a[9].size=10; a[9].price=2;
    int value[limit+1];
    string item[limit+1];
     
    for (int s=0; s<=limit; s++)
    {
        value[s]=0;         // 初期値
    }

    for (int i=0; i<n; i++)  // 品物の番号
    {                      
        for (int s=a[i].size; s<=limit; s++)  //  ナップのサイズ
	{
	    int p=s-a[i].size;   // 空きサイズ
            int newvalue=value[p]+a[i].price;

            if (newvalue>value[s])
	    {
	       // 最適解の更新
	       value[s]=newvalue;
	       item[s]=item[p]+a[i].name+",";
            }
        }
    }

    // 表示
    cout << "品物\t" << item[limit] << endl;
    cout << "価格\t" << value[limit] << endl;
}

コード:

#include <iostream>
#include <string>
 
using namespace std;
 
#define LIMIT 121  // ナップサックの重量制限値
#define N 10       // 品物の種類
 
struct Body 
{
    string name;   // 品名
    int size;      // 重さ 
    int price;     // 価格 
};
 
Body a[N] = {
    { "1",  20, 61 },
    { "2",  31, 89 },
    { "3",  15, 32 },
    { "4",  41, 47 },
    { "5",  16, 18 },
    { "6",  39, 42 },
    { "7",  13, 12 },
    { "8",  68, 45 },
    { "9",  15,  5 },
    { "10", 10,  2 },
};

int b[N], max_b[N];
int max_value;

void step(int i, int size, int value)
{
    if (size > LIMIT) return;
    if (i < N) {
        b[i] = 1; step(i + 1, size + a[i].size, value + a[i].price);
        b[i] = 0; step(i + 1, size, value);
    }
    else {
        if (value > max_value) {
            max_value = value;
            for (int i = 0; i < N; i++) max_b[i] = b[i];
        }
    }
}

int main()
{
    step(0, 0, 0); 
    cout << "品物\t";
    for (int i = 0; i < N; i++)
        if (max_b[i]) cout << a[i].name << ',';
    cout << "\n価格\t" << max_value << endl;
}

コード:

品物	1,2,3,5,6,
価格	242

コード:

#include <iostream>
#include <string>
 
using namespace std;
 
#define LIMIT 121  // ナップサックの重量制限値
#define N 10       // 品物の種類
 
struct Body {
    string name;   // 品名
    int size;      // 重さ 
    int price;     // 価格 
};
 
Body a[N] = {
    { "1",  20, 61 },
    { "2",  31, 89 },
    { "3",  15, 32 },
    { "4",  41, 47 },
    { "5",  16, 18 },
    { "6",  39, 42 },
    { "7",  13, 12 },
    { "8",  68, 45 },
    { "9",  15,  5 },
    { "10", 10,  2 },
};

int main()
{
    int b, max_b = 0, max_value = 0;
    for (b = 0; b < (1<<N); b++) {
        int i, size = 0, value = 0;
        for (i = 0; i < N; i++)
            if (b & (1<<i)) {
                size += a[i].size;
                if (size > LIMIT) break;
                value += a[i].price;
            }
        if (i == N && value > max_value)
            max_value = value, max_b = b;
    }
    cout << "品物\t";
    for (int c = 0, i = 0; i < N; i++)
        if (max_b & (1<<i))
            c && cout << ',', cout << a[i].name, c = 1;
    cout << "\n価格\t" << max_value << endl;
}