帮助解决程序背包问题的动态规划方法

Question

会编程的朋友"knapsack the dynamic programming method"和"C ++"会和我分享吗？

动态规划求解背包的算法：谢谢大家

"weight / value"方法的代码：

#include <conio.h>
#include <stdio.h>
#include <iostream>
#include <windows.h>
using namespace std;
void gotoxy(int x, int y)
{
    COORD pos;
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

    if (INVALID_HANDLE_VALUE != hConsole)
    {
        pos.X = x;
        pos.Y = y;

        SetConsoleCursorPosition(hConsole, pos);
    }
}

int wherey()
{
    CONSOLE_SCREEN_BUFFER_INFO csbi;
    COORD                      result;
    if (!GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbi))
        return -1;
    result = csbi.dwCursorPosition;
    return result.Y;
}

int wherex()
{
    CONSOLE_SCREEN_BUFFER_INFO csbi;
    COORD                      result;
    if (!GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbi))
        return -1;
    result = csbi.dwCursorPosition;
    return result.X;
}

void sortbypw(int p[], int w[], int n)
{
    int i, t, j;
    for (i = 0; i <= n - 1; i++)
        for (j = i + 1; j <= n; j++)
            if (((float)p[i] / w[i])<((float)p[j] / w[j]))
            {
        t = p[i];
        p[i] = p[j];
        p[j] = t;
        t = w[i];
        w[i] = w[j];
        w[j] = t;
    }
}

float knapsack(int p[], int w[], int n, int m)
{
    sortbypw(p, w, n);
    int w1 = m;
    int i = 0;
    float pp = 0;
    while (i <= n && w1>0)
    {
        if (w[i]<w1)
        {
            cout << " p : " << p[i];
            w1 -= w[i];
            pp += p[i];
            i++;
        }
        else
        {
            cout << " p : " << p[i];
            pp += w1*((float)p[i] / w[i]);
            w1 = 0;
        }
    }
    return pp;
}

void main()
{
    // Ali Aghajani 2015/06/07
    int p[100] = { 6, 12, 7, 18, 9, 30 };
    int w[100] = { 1, 5, 3, 9, 5, 20 };
    system("cls");
    cout << "If You Want Input Data Press (Y) Else Press (N) :";
    char ch = cin.get();
    if (ch == 'n')
        cout << "\n\n Arzesh Knapsack : " << knapsack(p, w, 5, 20);
    else
    {
        int n, m;
        cout << "\nEnter Weight Knapsack : ";
        cin >> m;
        cout << "Enter Num : ";
        cin >> n;
        for (int i = 0; i<n; i++)
        {
            cout << "Enter Arzesh : ";
            cin >> p[i];
            cout << "\nEnter Weight : ";
            cin >> w[i];
            gotoxy(20, wherey() - 2);
            cout << " P/W Is : " << (float)p[i] / w[i];
            gotoxy(1, wherey() + 2);
            cout << ".......................................\n";
        }
        cout << "\n\n Arzesh Knapsack : " << knapsack(p, w, n - 1, m);
    }
}

Answer 1

仓促判断！

对不起某些人！

我的问题，我回复：

#include <iostream>
#include <string>
using namespace std;
void main(){
    // Ali Aghajani 2015/06/08
    int i, w, W, n, p[50][2], B[50][50];
    string R[50][50];
    char end = 'y';
    while (end == 'y' || end == 'Y'){
        system("cls");
        cout << "Enter Weight Knapsack (Max Value=50): ";
        cin >> W;
        cout << "Enter Num Object (Max Value=50): ";
        cin >> n;
        cout << "\n";
        p[0][0] = p[0][1] = 0;
        for (w = 0; w <= W; w++){
            for (i = 0; i <= n; i++){
                R[w][i] = "";
            }
        }

        for (i = 1; i <= n; i++){
            cout << "\tItem[" << i << "] Arzash: ";
            cin >> p[i][0];
            cout << "\tItem[" << i << "] Weight: ";
            cin >> p[i][1];
            cout << "\n";
        }
        system("cls");
        cout << "\n\t     p| ";
        for (i = 1; i <= n; i++){
            if (i <= 9)
                cout << "0" << i << " ";
            else
                cout << i << " ";
        }
        cout << "\n\t       ";
        for (i = 1; i <= n; i++){
            cout << "---";
        }
        cout << "\n\tArzash| ";
        for (i = 1; i <= n; i++){
            if (p[i][0] <= 9)
                cout << "0" << p[i][0] << " ";
            else
                cout << p[i][0] << " ";
        }
        cout << "\n\tWeight| ";
        for (i = 1; i <= n; i++){
            if (p[i][0] <= 9)
                cout << "0" << p[i][1] << " ";
            else
                cout << p[i][1] << " ";
        }
        cout << "\n";
        for (w = 0; w <= W; w++){ B[w][0] = 0; }
        for (i = 0; i <= n; i++){ B[0][i] = 0; }
        for (i = 1; i <= n; i++){
            for (w = 1; w <= W; w++){
                if (p[i][1] <= w){
                    if (p[i][0] + B[w - p[i][1]][i - 1] > B[w][i - 1]){
                        B[w][i] = p[i][0] + B[w - p[i][1]][i - 1];
                        string k = std::to_string(i);
                        R[w][i] = R[w - p[i][1]][i - 1] + "p[" + k + "] ";
                    }
                    else{
                        B[w][i] = B[w][i - 1];
                        R[w][i] = R[w][i] + R[w][i - 1];
                    }
                }
                else{
                    B[w][i] = B[w][i - 1];
                    R[w][i] = R[w][i] + R[w][i - 1];
                }
            }
        }
        cout << "\n\tTable values: ";
        for (w = 0; w <= W; w++){
            for (i = 0; i <= n; i++){
                if (B[w][i] <= 9)
                    cout << "0" << B[w][i] << " ";
                else
                    cout << B[w][i] << " ";
            }
            cout << "\n\t              ";
        }

        cout << "\n\n\t# Arzash Knapsack: " << B[W][n];
        cout << "\n\n\t# Items: " << R[W][n];
        cout << "\n\n\n\tIf You Want Continue Press (Y) Else Press Key : ";
        cin >>end;
    }
}

帮助解决程序背包问题的动态规划方法

Helping to solve program knapsack the dynamic programming method

dynamic-programming

knapsack-problem