贪心算法 部分背包问题 0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支...
\u8d2a\u5fc3\u7b97\u6cd5 \u90e8\u5206\u80cc\u5305\u95ee\u9898\u3000\u3000[\u80cc\u5305\u95ee\u9898]\u6709\u4e00\u4e2a\u80cc\u5305\uff0c\u80cc\u5305\u5bb9\u91cf\u662fM=150\u3002\u67097\u4e2a\u7269\u54c1\uff0c\u7269\u54c1\u53ef\u4ee5\u5206\u5272\u6210\u4efb\u610f\u5927\u5c0f\u3002
\u3000\u3000\u8981\u6c42\u5c3d\u53ef\u80fd\u8ba9\u88c5\u5165\u80cc\u5305\u4e2d\u7684\u7269\u54c1\u603b\u4ef7\u503c\u6700\u5927\uff0c\u4f46\u4e0d\u80fd\u8d85\u8fc7\u603b\u5bb9\u91cf\u3002
\u3000\u3000\u7269\u54c1 A B C D E F G
\u3000\u3000\u91cd\u91cf 35 30 60 50 40 10 25
\u3000\u3000\u4ef7\u503c 10 40 30 50 35 40 30
\u3000\u3000\u5206\u6790\uff1a
\u3000\u3000\u76ee\u6807\u51fd\u6570\uff1a \u2211pi\u6700\u5927
\u3000\u3000\u7ea6\u675f\u6761\u4ef6\u662f\u88c5\u5165\u7684\u7269\u54c1\u603b\u91cd\u91cf\u4e0d\u8d85\u8fc7\u80cc\u5305\u5bb9\u91cf\uff1a\u2211wi<=M( M=150)
\u3000\u3000\uff081\uff09\u6839\u636e\u8d2a\u5fc3\u7684\u7b56\u7565\uff0c\u6bcf\u6b21\u6311\u9009\u4ef7\u503c\u6700\u5927\u7684\u7269\u54c1\u88c5\u5165\u80cc\u5305\uff0c\u5f97\u5230\u7684\u7ed3\u679c\u662f\u5426\u6700\u4f18\uff1f
\u3000\u3000\uff082\uff09\u6bcf\u6b21\u6311\u9009\u6240\u5360\u91cd\u91cf\u6700\u5c0f\u7684\u7269\u54c1\u88c5\u5165\u662f\u5426\u80fd\u5f97\u5230\u6700\u4f18\u89e3\uff1f
\u3000\u3000\uff083\uff09\u6bcf\u6b21\u9009\u53d6\u5355\u4f4d\u91cd\u91cf\u4ef7\u503c\u6700\u5927\u7684\u7269\u54c1\uff0c\u6210\u4e3a\u89e3\u672c\u9898\u7684\u7b56\u7565\u3002 ?
\u3000\u3000\u503c\u5f97\u6ce8\u610f\u7684\u662f\uff0c\u8d2a\u5fc3\u7b97\u6cd5\u5e76\u4e0d\u662f\u5b8c\u5168\u4e0d\u53ef\u4ee5\u4f7f\u7528\uff0c\u8d2a\u5fc3\u7b56\u7565\u4e00\u65e6\u7ecf\u8fc7\u8bc1\u660e\u6210\u7acb\u540e\uff0c\u5b83\u5c31\u662f\u4e00\u79cd\u9ad8\u6548\u7684\u7b97\u6cd5\u3002
\u3000\u3000\u8d2a\u5fc3\u7b97\u6cd5\u8fd8\u662f\u5f88\u5e38\u89c1\u7684\u7b97\u6cd5\u4e4b\u4e00\uff0c\u8fd9\u662f\u7531\u4e8e\u5b83\u7b80\u5355\u6613\u884c\uff0c\u6784\u9020\u8d2a\u5fc3\u7b56\u7565\u4e0d\u662f\u5f88\u56f0\u96be\u3002
\u3000\u3000\u53ef\u60dc\u7684\u662f\uff0c\u5b83\u9700\u8981\u8bc1\u660e\u540e\u624d\u80fd\u771f\u6b63\u8fd0\u7528\u5230\u9898\u76ee\u7684\u7b97\u6cd5\u4e2d\u3002
\u3000\u3000\u4e00\u822c\u6765\u8bf4\uff0c\u8d2a\u5fc3\u7b97\u6cd5\u7684\u8bc1\u660e\u56f4\u7ed5\u7740\uff1a\u6574\u4e2a\u95ee\u9898\u7684\u6700\u4f18\u89e3\u4e00\u5b9a\u7531\u5728\u8d2a\u5fc3\u7b56\u7565\u4e2d\u5b58\u5728\u7684\u5b50\u95ee\u9898\u7684\u6700\u4f18\u89e3\u5f97\u6765\u7684\u3002
\u3000\u3000\u5bf9\u4e8e\u4f8b\u9898\u4e2d\u76843\u79cd\u8d2a\u5fc3\u7b56\u7565\uff0c\u90fd\u662f\u65e0\u6cd5\u6210\u7acb\uff08\u65e0\u6cd5\u88ab\u8bc1\u660e\uff09\u7684\uff0c\u89e3\u91ca\u5982\u4e0b\uff1a
\u3000\u3000\uff081\uff09\u8d2a\u5fc3\u7b56\u7565\uff1a\u9009\u53d6\u4ef7\u503c\u6700\u5927\u8005\u3002\u53cd\u4f8b\uff1a
\u3000\u3000W=30
\u3000\u3000\u7269\u54c1\uff1aA B C
\u3000\u3000\u91cd\u91cf\uff1a28 12 12
\u3000\u3000\u4ef7\u503c\uff1a30 20 20
\u3000\u3000\u6839\u636e\u7b56\u7565\uff0c\u9996\u5148\u9009\u53d6\u7269\u54c1A\uff0c\u63a5\u4e0b\u6765\u5c31\u65e0\u6cd5\u518d\u9009\u53d6\u4e86\uff0c\u53ef\u662f\uff0c\u9009\u53d6B\u3001C\u5219\u66f4\u597d\u3002
\u3000\u3000\uff082\uff09\u8d2a\u5fc3\u7b56\u7565\uff1a\u9009\u53d6\u91cd\u91cf\u6700\u5c0f\u3002\u5b83\u7684\u53cd\u4f8b\u4e0e\u7b2c\u4e00\u79cd\u7b56\u7565\u7684\u53cd\u4f8b\u5dee\u4e0d\u591a\u3002
\u3000\u3000\uff083\uff09\u8d2a\u5fc3\u7b56\u7565\uff1a\u9009\u53d6\u5355\u4f4d\u91cd\u91cf\u4ef7\u503c\u6700\u5927\u7684\u7269\u54c1\u3002\u53cd\u4f8b\uff1a
\u3000\u3000W=30
\u3000\u3000\u7269\u54c1\uff1aA B C
\u3000\u3000\u91cd\u91cf\uff1a28 20 10
\u3000\u3000\u4ef7\u503c\uff1a28 20 10
\u3000\u3000\u6839\u636e\u7b56\u7565\uff0c\u4e09\u79cd\u7269\u54c1\u5355\u4f4d\u91cd\u91cf\u4ef7\u503c\u4e00\u6837\uff0c\u7a0b\u5e8f\u65e0\u6cd5\u4f9d\u636e\u73b0\u6709\u7b56\u7565\u4f5c\u51fa\u5224\u65ad\uff0c\u5982\u679c\u9009\u62e9A\uff0c\u5219\u7b54\u6848\u9519\u8bef\u3002
\u4e00.\u52a8\u6001\u89c4\u5212\u6c42\u89e30-1\u80cc\u5305\u95ee\u9898
/************************************************************************/
/* 0-1\u80cc\u5305\u95ee\u9898\uff1a
/* \u7ed9\u5b9an\u79cd\u7269\u54c1\u548c\u4e00\u4e2a\u80cc\u5305
/* \u7269\u54c1i\u7684\u91cd\u91cf\u4e3awi\uff0c\u5176\u4ef7\u503c\u4e3avi
/* \u80cc\u5305\u7684\u5bb9\u91cf\u4e3ac
/* \u5e94\u5982\u4f55\u9009\u62e9\u88c5\u5165\u80cc\u5305\u7684\u7269\u54c1\uff0c\u4f7f\u5f97\u88c5\u5165\u80cc\u5305\u4e2d\u7684\u7269\u54c1
/* \u7684\u603b\u4ef7\u503c\u6700\u5927\uff1f
/* \u6ce8\uff1a\u5728\u9009\u62e9\u88c5\u5165\u80cc\u5305\u7684\u7269\u54c1\u65f6\uff0c\u5bf9\u7269\u54c1i\u53ea\u6709\u4e24\u79cd\u9009\u62e9\uff0c
/* \u5373\u88c5\u5165\u6216\u4e0d\u88c5\u5165\u80cc\u5305\u3002\u4e0d\u80fd\u5c06\u7269\u54c1i\u88c5\u5165\u591a\u6b21\uff0c\u4e5f
/* \u4e0d\u80fd\u53ea\u88c5\u5165\u90e8\u5206\u7684\u7269\u54c1i\u3002
/*
/* 1. 0-1\u80cc\u5305\u95ee\u9898\u7684\u5f62\u5f0f\u5316\u63cf\u8ff0\uff1a
/* \u7ed9\u5b9ac>0, wi>0, vi>0, 0<=i<=n\uff0c\u8981\u6c42\u627e\u5230\u4e00\u4e2an\u5143\u7684
/* 0-1\u5411\u91cf(x1, x2, ..., xn), \u4f7f\u5f97\uff1a
/* max sum_{i=1 to n} (vi*xi),\u4e14\u6ee1\u8db3\u5982\u4e0b\u7ea6\u675f\uff1a
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi\u2208{0, 1}, 1<=i<=n
/*
/* 2. 0-1\u80cc\u5305\u95ee\u9898\u7684\u6c42\u89e3
/* 0-1\u80cc\u5305\u95ee\u9898\u5177\u6709\u6700\u4f18\u5b50\u7ed3\u6784\u6027\u8d28\u548c\u5b50\u95ee\u9898\u91cd\u53e0\u6027\u8d28\uff0c\u9002\u4e8e
/* \u91c7\u7528\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\u6c42\u89e3
/*
/* 2.1 \u6700\u4f18\u5b50\u7ed3\u6784\u6027\u8d28
/* \u8bbe(y1,y2,...,yn)\u662f\u7ed9\u5b9a0-1\u80cc\u5305\u95ee\u9898\u7684\u4e00\u4e2a\u6700\u4f18\u89e3\uff0c\u5219\u5fc5\u6709
/* \u7ed3\u8bba\uff0c(y2,y3,...,yn)\u662f\u5982\u4e0b\u5b50\u95ee\u9898\u7684\u4e00\u4e2a\u6700\u4f18\u89e3\uff1a
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi\u2208{0, 1}, 2<=i<=n
/* \u56e0\u4e3a\u5982\u82e5\u4e0d\u7136\uff0c\u5219\u8be5\u5b50\u95ee\u9898\u5b58\u5728\u4e00\u4e2a\u6700\u4f18\u89e3(z2,z3,...,zn)\uff0c
/* \u800c(y2,y3,...,yn)\u4e0d\u662f\u5176\u6700\u4f18\u89e3\u3002\u90a3\u4e48\u6709\uff1a
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* \u4e14\uff0cw1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* \u8fdb\u4e00\u6b65\u6709\uff1a
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* \u8fd9\u8bf4\u660e\uff1a(y1,z2,z3,...zn)\u662f\u6240\u7ed90-1\u80cc\u5305\u95ee\u9898\u7684\u66f4\u4f18\u89e3\uff0c\u90a3\u4e48
/* \u8bf4\u660e(y1,y2,...,yn)\u4e0d\u662f\u95ee\u9898\u7684\u6700\u4f18\u89e3\uff0c\u4e0e\u524d\u63d0\u77db\u76fe\uff0c\u6240\u4ee5\u6700\u4f18
/* \u5b50\u7ed3\u6784\u6027\u8d28\u6210\u7acb\u3002
/*
/* 2.2 \u5b50\u95ee\u9898\u91cd\u53e0\u6027\u8d28
/* \u8bbe\u6240\u7ed90-1\u80cc\u5305\u95ee\u9898\u7684\u5b50\u95ee\u9898 P(i,j)\u4e3a\uff1a
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk\u2208{0, 1}, i<=k<=n
/* \u95ee\u9898P(i,j)\u662f\u80cc\u5305\u5bb9\u91cf\u4e3aj\u3001\u53ef\u9009\u7269\u54c1\u4e3ai,i+1,...,n\u65f6\u7684\u5b50\u95ee\u9898
/* \u8bbem(i,j)\u662f\u5b50\u95ee\u9898P(i,j)\u7684\u6700\u4f18\u503c\uff0c\u5373\u6700\u5927\u603b\u4ef7\u503c\u3002\u5219\u6839\u636e\u6700\u4f18
/* \u5b50\u7ed3\u6784\u6027\u8d28\uff0c\u53ef\u4ee5\u5efa\u7acbm(i,j)\u7684\u9012\u5f52\u5f0f\uff1a
/* a. \u9012\u5f52\u521d\u59cb m(n,j)
/* //\u80cc\u5305\u5bb9\u91cf\u4e3aj\u3001\u53ef\u9009\u7269\u54c1\u53ea\u6709n\uff0c\u82e5\u80cc\u5305\u5bb9\u91cfj\u5927\u4e8e\u7269\u54c1n\u7684
/* //\u91cd\u91cf\uff0c\u5219\u76f4\u63a5\u88c5\u5165\uff1b\u5426\u5219\u65e0\u6cd5\u88c5\u5165\u3002
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. \u9012\u5f52\u5f0f m(i,j)
/* //\u80cc\u5305\u5bb9\u91cf\u4e3aj\u3001\u53ef\u9009\u7269\u54c1\u4e3ai,i+1,...,n
/* //\u5982\u679c\u80cc\u5305\u5bb9\u91cfj<wi\uff0c\u5219\u6839\u672c\u88c5\u4e0d\u8fdb\u7269\u54c1i\uff0c\u6240\u4ee5\u6709\uff1a
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //\u5982\u679cj>=wi\uff0c\u5219\u5728\u4e0d\u88c5\u7269\u54c1i\u548c\u88c5\u5165\u7269\u54c1i\u4e4b\u95f4\u505a\u51fa\u9009\u62e9
/* \u4e0d\u88c5\u7269\u54c1i\u7684\u6700\u4f18\u503c\uff1am(i+1,j)
/* \u88c5\u5165\u7269\u54c1i\u7684\u6700\u4f18\u503c\uff1am(i+1, j-wi) + vi
/* \u6240\u4ee5\uff1a
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//\u9012\u5f52\u521d\u59cb\u6761\u4ef6
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i\u4ece2\u5230n-1\uff0c\u5206\u522b\u5bf9j>=wi\u548c0<=j<wi\u5373\u4f7fm(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack(v, w, c, n, ppm);
TraceBack(ppm, w, c, n, x);
return 0;
}
\u4e8c.\u8d2a\u5fc3\u7b97\u6cd5\u6c42\u89e30-1\u80cc\u5305\u95ee\u9898
1.\u8d2a\u5fc3\u6cd5\u7684\u57fa\u672c\u601d\u8def\uff1a
\u2014\u2014\u4ece\u95ee\u9898\u7684\u67d0\u4e00\u4e2a\u521d\u59cb\u89e3\u51fa\u53d1\u9010\u6b65\u903c\u8fd1\u7ed9\u5b9a\u7684\u76ee\u6807\uff0c\u4ee5\u5c3d\u53ef\u80fd\u5feb\u7684\u5730\u6c42\u5f97\u66f4\u597d\u7684\u89e3\u3002\u5f53\u8fbe\u5230\u67d0\u7b97\u6cd5\u4e2d\u7684\u67d0\u4e00\u6b65\u4e0d\u80fd\u518d\u7ee7\u7eed\u524d\u8fdb\u65f6\uff0c\u7b97\u6cd5\u505c\u6b62\u3002
\u8be5\u7b97\u6cd5\u5b58\u5728\u95ee\u9898\uff1a
1).\u4e0d\u80fd\u4fdd\u8bc1\u6c42\u5f97\u7684\u6700\u540e\u89e3\u662f\u6700\u4f73\u7684\uff1b
2).\u4e0d\u80fd\u7528\u6765\u6c42\u6700\u5927\u6216\u6700\u5c0f\u89e3\u95ee\u9898\uff1b
3).\u53ea\u80fd\u6c42\u6ee1\u8db3\u67d0\u4e9b\u7ea6\u675f\u6761\u4ef6\u7684\u53ef\u884c\u89e3\u7684\u8303\u56f4\u3002
\u5b9e\u73b0\u8be5\u7b97\u6cd5\u7684\u8fc7\u7a0b\uff1a
\u4ece\u95ee\u9898\u7684\u67d0\u4e00\u521d\u59cb\u89e3\u51fa\u53d1\uff1b
while \u80fd\u671d\u7ed9\u5b9a\u603b\u76ee\u6807\u524d\u8fdb\u4e00\u6b65 do
\u3000\u3000 \u6c42\u51fa\u53ef\u884c\u89e3\u7684\u4e00\u4e2a\u89e3\u5143\u7d20\uff1b
\u7531\u6240\u6709\u89e3\u5143\u7d20\u7ec4\u5408\u6210\u95ee\u9898\u7684\u4e00\u4e2a\u53ef\u884c\u89e3\uff1b
2.\u4f8b\u9898\u5206\u6790
1).[\u80cc\u5305\u95ee\u9898]\u6709\u4e00\u4e2a\u80cc\u5305\uff0c\u80cc\u5305\u5bb9\u91cf\u662fM=150\u3002\u67097\u4e2a\u7269\u54c1\uff0c\u7269\u54c1\u53ef\u4ee5\u5206\u5272\u6210\u4efb\u610f\u5927\u5c0f\u3002
\u8981\u6c42\u5c3d\u53ef\u80fd\u8ba9\u88c5\u5165\u80cc\u5305\u4e2d\u7684\u7269\u54c1\u603b\u4ef7\u503c\u6700\u5927\uff0c\u4f46\u4e0d\u80fd\u8d85\u8fc7\u603b\u5bb9\u91cf\u3002
\u7269\u54c1 A B C D E F G
\u91cd\u91cf 35 30 60 50 40 10 25
\u4ef7\u503c 10 40 30 50 35 40 30
\u5206\u6790\uff1a
\u76ee\u6807\u51fd\u6570\uff1a \u2211pi\u6700\u5927
\u7ea6\u675f\u6761\u4ef6\u662f\u88c5\u5165\u7684\u7269\u54c1\u603b\u91cd\u91cf\u4e0d\u8d85\u8fc7\u80cc\u5305\u5bb9\u91cf\uff1a\u2211wi<=M( M=150)
\uff081\uff09\u6839\u636e\u8d2a\u5fc3\u7684\u7b56\u7565\uff0c\u6bcf\u6b21\u6311\u9009\u4ef7\u503c\u6700\u5927\u7684\u7269\u54c1\u88c5\u5165\u80cc\u5305\uff0c\u5f97\u5230\u7684\u7ed3\u679c\u662f\u5426\u6700\u4f18\uff1f
\uff082\uff09\u6bcf\u6b21\u6311\u9009\u6240\u5360\u7a7a\u95f4\u6700\u5c0f\u7684\u7269\u54c1\u88c5\u5165\u662f\u5426\u80fd\u5f97\u5230\u6700\u4f18\u89e3\uff1f
\uff083\uff09\u6bcf\u6b21\u9009\u53d6\u5355\u4f4d\u5bb9\u91cf\u4ef7\u503c\u6700\u5927\u7684\u7269\u54c1\uff0c\u6210\u4e3a\u89e3\u672c\u9898\u7684\u7b56\u7565\u3002
(\u73af\u5883:c++)
#include
#define max 100 //\u6700\u591a\u7269\u54c1\u6570
void sort (int n,float a[max],float b[max]) //\u6309\u4ef7\u503c\u5bc6\u5ea6\u6392\u5e8f
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1\u4e3a\u80cc\u5305\u5269\u4f59\u53ef\u88c5\u8f7d\u91cd\u91cf
int i;
sort(n,v,w); //\u7269\u54c1\u6309\u4ef7\u503c\u5bc6\u5ea6\u6392\u5e8f
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]\u4e3a1\u65f6\uff0c\u7269\u54c1i\u5728\u89e3\u4e2d
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"\u8bf7\u8f93\u5165n\u548climitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //\u7269\u54c1\u9009\u62e9\u60c5\u51b5\u8868\u521d\u59cb\u5316\u4e3a0
cout<<"\u8bf7\u4f9d\u6b21\u8f93\u5165\u7269\u54c1\u7684\u4ef7\u503c\uff1a"<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"\u8bf7\u4f9d\u6b21\u8f93\u5165\u7269\u54c1\u7684\u91cd\u91cf\uff1a"<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"\u80cc\u5305\u7684\u603b\u91cd\u91cf\u4e3a\uff1a"<<totalw<<endl; //\u80cc\u5305\u6240\u88c5\u8f7d\u603b\u91cd\u91cf
cout<<"\u80cc\u5305\u7684\u603b\u4ef7\u503c\u4e3a\uff1a"<<totalv<<endl; //\u80cc\u5305\u7684\u603b\u4ef7\u503c
}
\u4e09.\u56de\u6eaf\u7b97\u6cd5\u6c42\u89e30-1\u80cc\u5305\u95ee\u9898
1.0-l\u80cc\u5305\u95ee\u9898\u662f\u5b50\u96c6\u9009\u53d6\u95ee\u9898\u3002
\u4e00\u822c\u60c5\u51b5\u4e0b\uff0c0-1\u80cc\u5305\u95ee\u9898\u662fNP\u96be\u9898\u30020-1\u80cc\u5305
\u95ee\u9898\u7684\u89e3\u7a7a\u95f4\u53ef\u7528\u5b50\u96c6\u6811\u8868\u793a\u3002\u89e30-1\u80cc\u5305\u95ee\u9898\u7684\u56de\u6eaf\u6cd5\u4e0e\u88c5\u8f7d\u95ee\u9898\u7684\u56de\u6eaf\u6cd5\u5341\u5206\u7c7b
\u4f3c\u3002\u5728\u641c\u7d22\u89e3\u7a7a\u95f4\u6811\u65f6\uff0c\u53ea\u8981\u5176\u5de6\u513f\u5b50\u7ed3\u70b9\u662f\u4e00\u4e2a\u53ef\u884c\u7ed3\u70b9\uff0c\u641c\u7d22\u5c31\u8fdb\u5165\u5176\u5de6\u5b50\u6811\u3002\u5f53
\u53f3\u5b50\u6811\u6709\u53ef\u80fd\u5305\u542b\u6700\u4f18\u89e3\u65f6\u624d\u8fdb\u5165\u53f3\u5b50\u6811\u641c\u7d22\u3002\u5426\u5219\u5c06\u53f3\u5b50\u6811\u526a\u53bb\u3002\u8bber\u662f\u5f53\u524d\u5269\u4f59
\u7269\u54c1\u4ef7\u503c\u603b\u548c\uff1bcp\u662f\u5f53\u524d\u4ef7\u503c\uff1bbestp\u662f\u5f53\u524d\u6700\u4f18\u4ef7\u503c\u3002\u5f53cp+r\u2264bestp\u65f6\uff0c\u53ef\u526a\u53bb\u53f3
\u5b50\u6811\u3002\u8ba1\u7b97\u53f3\u5b50\u6811\u4e2d\u89e3\u7684\u4e0a\u754c\u7684\u66f4\u597d\u65b9\u6cd5\u662f\u5c06\u5269\u4f59\u7269\u54c1\u4f9d\u5176\u5355\u4f4d\u91cd\u91cf\u4ef7\u503c\u6392\u5e8f\uff0c\u7136\u540e
\u4f9d\u6b21\u88c5\u5165\u7269\u54c1\uff0c\u76f4\u81f3\u88c5\u4e0d\u4e0b\u65f6\uff0c\u518d\u88c5\u5165\u8be5\u7269\u54c1\u7684\u4e00\u90e8\u5206\u800c\u88c5\u6ee1\u80cc\u5305\u3002\u7531\u6b64\u5f97\u5230\u7684\u4ef7\u503c\u662f
\u53f3\u5b50\u6811\u4e2d\u89e3\u7684\u4e0a\u754c\u3002
2.\u89e3\u51b3\u529e\u6cd5\u601d\u8def\uff1a
\u4e3a\u4e86\u4fbf\u4e8e\u8ba1\u7b97\u4e0a\u754c\uff0c\u53ef\u5148\u5c06\u7269\u54c1\u4f9d\u5176\u5355\u4f4d\u91cd\u91cf\u4ef7\u503c\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\uff0c\u6b64\u540e\u53ea\u8981\u987a\u5e8f\u8003
\u5bdf\u5404\u7269\u54c1\u5373\u53ef\u3002\u5728\u5b9e\u73b0\u65f6\uff0c\u7531bound\u8ba1\u7b97\u5f53\u524d\u7ed3\u70b9\u5904\u7684\u4e0a\u754c\u3002\u5728\u641c\u7d22\u89e3\u7a7a\u95f4\u6811\u65f6\uff0c\u53ea\u8981\u5176\u5de6\u513f\u5b50\u8282\u70b9\u662f\u4e00\u4e2a\u53ef\u884c\u7ed3\u70b9\uff0c\u641c\u7d22\u5c31\u8fdb\u5165\u5de6\u5b50\u6811\uff0c\u5728\u53f3\u5b50\u6811\u4e2d\u6709\u53ef\u80fd\u5305\u542b\u6700\u4f18\u89e3\u662f\u624d\u8fdb\u5165\u53f3\u5b50\u6811\u641c\u7d22\u3002\u5426\u5219\u5c06\u53f3\u5b50\u6811\u526a\u53bb\u3002
\u56de\u6eaf\u6cd5\u662f\u4e00\u4e2a\u65e2\u5e26\u6709\u7cfb\u7edf\u6027\u53c8\u5e26\u6709\u8df3\u8dc3\u6027\u7684\u7684\u641c\u7d22\u7b97\u6cd5\u3002\u5b83\u5728\u5305\u542b\u95ee\u9898\u7684\u6240\u6709\u89e3\u7684\u89e3\u7a7a\u95f4\u6811\u4e2d\uff0c\u6309\u7167\u6df1\u5ea6\u4f18\u5148\u7684\u7b56\u7565\uff0c\u4ece\u6839\u7ed3\u70b9\u51fa\u53d1\u641c\u7d22\u89e3\u7a7a\u95f4\u6811\u3002\u7b97\u6cd5\u641c\u7d22\u81f3\u89e3\u7a7a\u95f4\u6811\u7684\u4efb\u4e00\u7ed3\u70b9\u65f6\uff0c\u603b\u662f\u5148\u5224\u65ad\u8be5\u7ed3\u70b9\u662f\u5426\u80af\u5b9a\u4e0d\u5305\u542b\u95ee\u9898\u7684\u89e3\u3002\u5982\u679c\u80af\u5b9a\u4e0d\u5305\u542b\uff0c\u5219\u8df3\u8fc7\u5bf9\u4ee5\u8be5\u7ed3\u70b9\u4e3a\u6839\u7684\u5b50\u6811\u7684\u7cfb\u7edf\u641c\u7d22\uff0c\u9010\u5c42\u5411\u5176\u7956\u5148\u7ed3\u70b9\u56de\u6eaf\u3002\u5426\u5219\uff0c\u8fdb\u5165\u8be5\u5b50\u6811\uff0c\u7ee7\u7eed\u6309\u6df1\u5ea6\u4f18\u5148\u7684\u7b56\u7565\u8fdb\u884c\u641c\u7d22\u3002\u56de\u6eaf\u6cd5\u5728\u7528\u6765\u6c42\u95ee\u9898\u7684\u6240\u6709\u89e3\u65f6\uff0c\u8981\u56de\u6eaf\u5230\u6839\uff0c\u4e14\u6839\u7ed3\u70b9\u7684\u6240\u6709\u5b50\u6811\u90fd\u5df2\u88ab\u641c\u7d22\u904d\u624d\u7ed3\u675f\u3002\u800c\u56de\u6eaf\u6cd5\u5728\u7528\u6765\u6c42\u95ee\u9898\u7684\u4efb\u4e00\u89e3\u65f6\uff0c\u53ea\u8981\u641c\u7d22\u5230\u95ee\u9898\u7684\u4e00\u4e2a\u89e3\u5c31\u53ef\u4ee5\u7ed3\u675f\u3002\u8fd9\u79cd\u4ee5\u6df1\u5ea6\u4f18\u5148\u7684\u65b9\u5f0f\u7cfb\u7edf\u5730\u641c\u7d22\u95ee\u9898\u7684\u89e3\u7684\u7b97\u6cd5\u79f0\u4e3a\u56de\u6eaf\u6cd5\uff0c\u5b83\u9002\u7528\u4e8e\u89e3\u4e00\u4e9b\u7ec4\u5408\u6570\u8f83\u5927\u7684\u95ee\u9898\u3002
2.\u7b97\u6cd5\u6846\u67b6\uff1a
a.\u95ee\u9898\u7684\u89e3\u7a7a\u95f4\uff1a\u5e94\u7528\u56de\u6eaf\u6cd5\u89e3\u95ee\u9898\u65f6\uff0c\u9996\u5148\u5e94\u660e\u786e\u5b9a\u4e49\u95ee\u9898\u7684\u89e3\u7a7a\u95f4\u3002\u95ee\u9898\u7684\u89e3\u7a7a\u95f4\u5e94\u5230\u5c11\u5305\u542b\u95ee\u9898\u7684\u4e00\u4e2a\uff08\u6700\u4f18\uff09\u89e3\u3002
b.\u56de\u6eaf\u6cd5\u7684\u57fa\u672c\u601d\u60f3\uff1a\u786e\u5b9a\u4e86\u89e3\u7a7a\u95f4\u7684\u7ec4\u7ec7\u7ed3\u6784\u540e\uff0c\u56de\u6eaf\u6cd5\u5c31\u4ece\u5f00\u59cb\u7ed3\u70b9\uff08\u6839\u7ed3\u70b9\uff09\u51fa\u53d1\uff0c\u4ee5\u6df1\u5ea6\u4f18\u5148\u7684\u65b9\u5f0f\u641c\u7d22\u6574\u4e2a\u89e3\u7a7a\u95f4\u3002\u8fd9\u4e2a\u5f00\u59cb\u7ed3\u70b9\u5c31\u6210\u4e3a\u4e00\u4e2a\u6d3b\u7ed3\u70b9\uff0c\u540c\u65f6\u4e5f\u6210\u4e3a\u5f53\u524d\u7684\u6269\u5c55\u7ed3\u70b9\u3002\u5728\u5f53\u524d\u7684\u6269\u5c55\u7ed3\u70b9\u5904\uff0c\u641c\u7d22\u5411\u7eb5\u6df1\u65b9\u5411\u79fb\u81f3\u4e00\u4e2a\u65b0\u7ed3\u70b9\u3002\u8fd9\u4e2a\u65b0\u7ed3\u70b9\u5c31\u6210\u4e3a\u4e00\u4e2a\u65b0\u7684\u6d3b\u7ed3\u70b9\uff0c\u5e76\u6210\u4e3a\u5f53\u524d\u6269\u5c55\u7ed3\u70b9\u3002\u5982\u679c\u5728\u5f53\u524d\u7684\u6269\u5c55\u7ed3\u70b9\u5904\u4e0d\u80fd\u518d\u5411\u7eb5\u6df1\u65b9\u5411\u79fb\u52a8\uff0c\u5219\u5f53\u524d\u6269\u5c55\u7ed3\u70b9\u5c31\u6210\u4e3a\u6b7b\u7ed3\u70b9\u3002\u6362\u53e5\u8bdd\u8bf4\uff0c\u8fd9\u4e2a\u7ed3\u70b9\u4e0d\u518d\u662f\u4e00\u4e2a\u6d3b\u7ed3\u70b9\u3002\u6b64\u65f6\uff0c\u5e94\u5f80\u56de\u79fb\u52a8\uff08\u56de\u6eaf\uff09\u81f3\u6700\u8fd1\u7684\u4e00\u4e2a\u6d3b\u7ed3\u70b9\u5904\uff0c\u5e76\u4f7f\u8fd9\u4e2a\u6d3b\u7ed3\u70b9\u6210\u4e3a\u5f53\u524d\u7684\u6269\u5c55\u7ed3\u70b9\u3002\u56de\u6eaf\u6cd5\u5373\u4ee5\u8fd9\u79cd\u5de5\u4f5c\u65b9\u5f0f\u9012\u5f52\u5730\u5728\u89e3\u7a7a\u95f4\u4e2d\u641c\u7d22\uff0c\u76f4\u81f3\u627e\u5230\u6240\u8981\u6c42\u7684\u89e3\u6216\u89e3\u7a7a\u95f4\u4e2d\u5df2\u6ca1\u6709\u6d3b\u7ed3\u70b9\u65f6\u4e3a\u6b62\u3002
3.\u8fd0\u7528\u56de\u6eaf\u6cd5\u89e3\u9898\u901a\u5e38\u5305\u542b\u4ee5\u4e0b\u4e09\u4e2a\u6b65\u9aa4\uff1a
a.\u9488\u5bf9\u6240\u7ed9\u95ee\u9898\uff0c\u5b9a\u4e49\u95ee\u9898\u7684\u89e3\u7a7a\u95f4\uff1b
b.\u786e\u5b9a\u6613\u4e8e\u641c\u7d22\u7684\u89e3\u7a7a\u95f4\u7ed3\u6784\uff1b
c.\u4ee5\u6df1\u5ea6\u4f18\u5148\u7684\u65b9\u5f0f\u641c\u7d22\u89e3\u7a7a\u95f4\uff0c\u5e76\u4e14\u5728\u641c\u7d22\u8fc7\u7a0b\u4e2d\u7528\u526a\u679d\u51fd\u6570\u907f\u514d\u65e0\u6548\u641c\u7d22\uff1b
#include
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//\u80cc\u5305\u5bb9\u91cf
int n; //\u7269\u54c1\u6570
int *w;//\u7269\u54c1\u91cd\u91cf\u6570\u7ec4
int *p;//\u7269\u54c1\u4ef7\u503c\u6570\u7ec4
int cw;//\u5f53\u524d\u91cd\u91cf
int cp;//\u5f53\u524d\u4ef7\u503c
int bestp;//\u5f53\u524d\u6700\u4f18\u503c
int *bestx;//\u5f53\u524d\u6700\u4f18\u89e3
int *x;//\u5f53\u524d\u89e3
};
int Knap::Bound(int i)
{
//\u8ba1\u7b97\u4e0a\u754c
int cleft=c-cw;//\u5269\u4f59\u5bb9\u91cf
int b=cp;
//\u4ee5\u7269\u54c1\u5355\u4f4d\u91cd\u91cf\u4ef7\u503c\u9012\u51cf\u5e8f\u88c5\u5165\u7269\u54c1
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//\u88c5\u6ee1\u80cc\u5305
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //\u641c\u7d22\u5de6\u5b50\u6811
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//\u641c\u7d22\u53f3\u5b50\u6811
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//\u4e3aKnap::Backtrack\u521d\u59cb\u5316
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//\u88c5\u5165\u6240\u6709\u7269\u54c1
//\u4f9d\u7269\u54c1\u5355\u4f4d\u91cd\u91cf\u6392\u5e8f
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//\u56de\u6eaf\u641c\u7d22
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1\u80cc\u5305\u95ee\u9898\u2014\u2014\u56de\u6eaf\u6cd5 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"\u8bf7\u8f93\u5165\u80cc\u5305\u5bb9\u91cf(c)\uff1a"<<endl;
cin>>c;
cout<<"\u8bf7\u8f93\u5165\u7269\u54c1\u7684\u4e2a\u6570(n)\uff1a"<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"\u8bf7\u8f93\u5165\u7269\u54c1\u7684\u4ef7\u503c(p)\uff1a"<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"\u8bf7\u8f93\u5165\u7269\u54c1\u7684\u91cd\u91cf(w)\uff1a"<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"\u6700\u4f18\u89e3\u4e3a(bestx)\uff1a"<<endl;
cout<<"\u6700\u4f18\u503c\u4e3a(bestp)\uff1a"<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] \u91cd\u65b0\u5f00\u59cb"<<endl;
cout<<"[q] \u9000\u51fa"<<endl;
cin>>k;
}
\u56db.\u5206\u652f\u9650\u754c\u6cd5\u6c42\u89e30-1\u80cc\u5305\u95ee\u9898
1.\u95ee\u9898\u63cf\u8ff0\uff1a\u5df2\u77e5\u6709N\u4e2a\u7269\u54c1\u548c\u4e00\u4e2a\u53ef\u4ee5\u5bb9\u7eb3M\u91cd\u91cf\u7684\u80cc\u5305\uff0c\u6bcf\u79cd\u7269\u54c1I\u7684\u91cd\u91cf\u4e3aWEIGHT\uff0c\u4e00\u4e2a\u53ea\u80fd\u5168\u653e\u5165\u6216\u8005\u4e0d\u653e\u5165\uff0c\u6c42\u89e3\u5982\u4f55\u653e\u5165\u7269\u54c1\uff0c\u53ef\u4ee5\u4f7f\u80cc\u5305\u91cc\u7684\u7269\u54c1\u7684\u603b\u6548\u76ca\u6700\u5927\u3002
2.\u8bbe\u8ba1\u601d\u60f3\u4e0e\u5206\u6790\uff1a\u5bf9\u7269\u54c1\u7684\u9009\u53d6\u4e0e\u5426\u6784\u6210\u4e00\u68f5\u89e3\u6811\uff0c\u5de6\u5b50\u6811\u8868\u793a\u4e0d\u88c5\u5165\uff0c\u53f3\u8868\u793a\u88c5\u5165\uff0c\u901a\u8fc7\u68c0\u7d22\u95ee\u9898\u7684\u89e3\u6811\u5f97\u51fa\u6700\u4f18\u89e3\uff0c\u5e76\u7528\u7ed3\u70b9\u4e0a\u754c\u6740\u6b7b\u4e0d\u7b26\u5408\u8981\u6c42\u7684\u7ed3\u70b9\u3002
#include
struct good
{
int weight;
int benefit;
int flag;//\u662f\u5426\u53ef\u4ee5\u88c5\u5165\u6807\u8bb0
};
int number=0;//\u7269\u54c1\u6570\u91cf
int upbound=0;
int curp=0, curw=0;//\u5f53\u524d\u6548\u76ca\u503c\u4e0e\u91cd\u91cf
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"\u8bf7\u8f93\u5165\u7b2c\u4ef6"<<i+1<<"\u7269\u54c1\u7684\u91cd\u91cf:";
cin>>bag[i].weight;
cout<<"\u8bf7\u8f93\u5165\u7b2c\u4ef6"<<i+1<<"\u7269\u54c1\u7684\u6548\u76ca:";
cin>>bag[i].benefit;
bag[i].flag=0;//\u521d\u59cb\u6807\u5fd7\u4e3a\u4e0d\u88c5\u5165\u80cc\u5305
cout<<endl;
}
}
int getbound(int num, int *bound_u)//\u8fd4\u56de\u672c\u7ed3\u70b9\u7684c\u9650\u754c\u548cu\u9650\u754c
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//\u5f53\u524d\u7ed3\u70b9\u7684c\u9650\u754c\u548cu\u9650\u754c
for(int i=0; i<number; i++)//\u9010\u5c42\u904d\u5386\u89e3\u6811\u51b3\u5b9a\u662f\u5426\u88c5\u5165\u5404\u4e2a\u7269\u54c1
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//\u904d\u5386\u5de6\u5b50\u6811
upbound=bound_u;//\u66f4\u6539\u5df2\u6709u\u9650\u754c,\u4e0d\u66f4\u6539\u6807\u5fd7
if( getbound(i, &bound_u)>bound_c )//\u904d\u5386\u53f3\u5b50\u6811
//\u82e5\u88c5\u5165\uff0c\u5224\u65ad\u53f3\u5b50\u6811\u7684c\u9650\u754c\u662f\u5426\u5927\u4e8e\u5de6\u5b50\u6811\u6839\u7684c\u9650\u754c\uff0c\u662f\u5219\u88c5\u5165
{
upbound=bound_u;//\u66f4\u6539\u5df2\u6709u\u9650\u754c
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//\u4ece\u5df2\u6709\u91cd\u91cf\u548c\u6548\u76ca\u52a0\u4e0a\u65b0\u7269\u54c1
bag[i].flag=1;//\u6807\u8bb0\u4e3a\u88c5\u5165
}
}
}
void Display()
{
cout<<"\u53ef\u4ee5\u653e\u5165\u80cc\u5305\u7684\u7269\u54c1\u7684\u7f16\u53f7\u4e3a\uff1a";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
(1)背包问题最优值的结构
动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动态规划的显著特征。
对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力为 m-w[i] 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包问题具有最优子结构。
(2)递归地定义最优值
动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原问题的最优值。对背包问题而言，有状态转移方程：
／max{s[k-w[i]]+v[i]}(其中1≤i≤n，且k-w[i]≥0)
s[k]= 若k>0且存在1≤i≤n使k-w[i]≥0，
＼ 0 否则。
有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输入背包的负重能力k，返回对应的子背包问题的最优值s[k]：
对每件物品，以价值排序，每次优先选取价值大的，若物品选光则选次大的，直到背包装不下。
证明：
对第i件物品，若它是当前能选的物品中价值最大的，则选一公斤的该物品总比选一公斤的其他物品价值大。若你选取了一公斤价值为V1的物品，剩下了一公斤价值为V2的物品，而V2>V1，则只要将
两物品交换则能构造出一个更优的解，由此可知，上述的贪心是正确的。
不是很明白..
baidu
扩展阅读：扫一扫题目出答案 ... 背包问题及解决办法 ... 贪心算法01背包问题 ... 贪心算法活动安排问题 ... 贪心法解01背包问题 ... 贪心算法最优装载问题 ... 贪心算法主要解决哪些问题 ... 十大最难智力题 ... 贪心算法解决旅行商问题 ...
