使用c++编写设有编号为1、2、…、n的n个物品，它们的重量分别为w1、w2、…、wn，价值分别为v1、v2、…、vn，其中wi、vi（1≤i≤n）均为正数。 有一个背包可以携带的最大重量不超过W。求解目标：在不超过背包负重的前提下，使背包装入的总价值最大。 函数接口定义： void Knap() 裁判测试程序样例： //求解背包问题的算法 #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define MAXN 51 //问题表示 int n; double W; //限重 struct NodeType { int no; double w; double v; double p; //p=v/w float x; bool operator<(const NodeType &s) const { return p>s.p; //按p递减排序 } }; NodeType A[MAXN]={{0}}; //下标0不用 //求解结果表示 double V; //最大价值 bool cmp(const NodeType &a,const NodeType &b) { return a.no<b.no; } void Knap(); int main() { cin>>n>>W; for(int i=1;i<=n;i++) { cin>>A[i].no>>A[i].w>>A[i].v;A[i].x=0; } for (int i=1;i<=n;i++) //求v/w A[i].p=A[i].v/A[i].w; sort(A+1,A+n+1); //排序 Knap(); sort(A+1,A+n+1,cmp); for(int j=1;j<=n;j++) cout<<A[j].no<<" "<<A[j].x*A[j].v<<endl; cout<<V; return 0; } /* 请在这里填写答案 */ 输入格式: 第一行物品数n和背包容量W，接着的n行中输入每个物品的编号，重量和价值。 输出格式: 输出装入背包的物品信息，共n行，按物品编号递增排序的物品编号及价值（物品编号从1开始）。最后一行输出总价值。 输入样例1: 5 100 1 10 20 2 20 30 3 30 66 4 40 40 5 50 60 输出样例1: 1 20 2 30 3 66 4 0 5 48 164

下面是使用c++编写的背包问题求解算法：

#include <iostream>
#include <algorithm>
using namespace std;

struct NodeType {
    int no;
    double w;
    double v;
    double p; //p=v/w
    float x;
    bool operator<(const NodeType &s) const {
        return p > s.p; //按p递减排序
    }
};

NodeType A[51] = {{0}}; //下标0不用
double V = 0.0;         //最大价值

bool cmp(const NodeType &a, const NodeType &b) {
    return a.no < b.no;
}

void Knap(int n, double W) {
    for (int i = 1; i <= n; i++) //求v/w
        A[i].p = A[i].v / A[i].w;
    sort(A + 1, A + n + 1); //排序
    for (int i = 1; i <= n; i++)
        A[i].x = 0.0;
    for (int i = 1; i <= n; i++) {
        if (A[i].w <= W) {
            A[i].x = 1.0;
            W -= A[i].w;
            V += A[i].v;
        } else {
            A[i].x = W / A[i].w;
            V += A[i].x * A[i].v;
            break;
        }
    }
}

int main() {
    int n;
    double W;
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        cin >> A[i].no >> A[i].w >> A[i].v;
        A[i].x = 0;
    }
    Knap(n, W);
    sort(A + 1, A + n + 1, cmp);
    for (int j = 1; j <= n; j++)
        printf("%d %.0f\n", A[j].no, A[j].x * A[j].v);
    printf("%.0f", V);

    return 0;
}