首页 > 试题广场 >

考虑一个有n=8个物品的背包问题实例,背包的容量m=110,

[单选题]
考虑一个有n=8个物品的背包问题实例,背包的容量m=110,P(价值)=(11,21,31,33,43,43,55,65),并且w(重量)=(1,11,21,23,33,43,45,55),请问不超过m的情况下,最大的放入价值是多少()

  • 169
  • 159
  • 149
  • 139
推荐
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define M 111
#define N 9

int max(int x, int y)
{
    return x>y?x:y;
}
int main()
{
    int i,j;
    int w[]={0,1,11,21,23,33,43,45,55};
    int p[]={0,11,21,31,33,43,43,55,65};
    int dp[N][M]={0};
    for(i=1;i<N;i++)
    {
        for(j=1;j<M;j++)
        {
            if(w[i]>j)
            {
                dp[i][j]=dp[i-1][j];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
            }

        }
    }
    cout <<dp[8][110];
    return 0;
}

编辑于 2017-05-24 15:54:03 回复(1)
如果是0,1背包问题的话,
最大价值应为151.
# A Dynamic Programming based Python Program for 0-1 Knapsack problem
# Returns the maximum value that can be put in a knapsack of capacity W
def knapSack(W, wt, val, n):
	K = [[0 for x in range(W+1)] for x in range(n+1)]

	# Build table K[][] in bottom up manner
	for i in range(n+1):
		for w in range(W+1):
			if i==0 or w==0:
				K[i][w] = 0
			elif wt[i-1] <= w:
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
			else:
				K[i][w] = K[i-1][w]

	return K[n][W]

# Driver program to test above function
val = [11,21,31,33,43,43,55,65]
wt = [1,11,21,23,33,43,45,55]
W = 110
n = len(val)
print(knapSack(W, wt, val, n))

# This code is contributed by Bhavya Jain


发表于 2017-07-19 10:47:21 回复(0)
const weightArr = [1, 11, 21, 23, 33, 43, 45, 55]
const priceArr = [11, 21, 31, 33, 43, 43, 55, 65]

function bugQuestion(arr = weightArr, max = 110) {
    let dpArr = Array.from({ length: arr.length }, _ => Array.from({ length: max }))
    dpArr[-1] = Array.from({ length: max + 1 }, _ => 0) // 增加负一行简化判断流程
    for (let i = 0; i < dpArr.length; i++) {
        for (let j = 0; j <= max; j++) {
            if (weightArr[i] > j) { // 已经放不下了
                dpArr[i][j] = dpArr[i - 1][j]
            } else {
                dpArr[i][j] = Math.max(dpArr[i - 1][j], dpArr[i - 1][j - weightArr[i]] + priceArr[i])
            }
        }
    }
    // 下面的代码用来判断选择了什么
    let selectArr = [], tempM = max, selectWeight = 0
    for (let i = dpArr.length - 1; i >= 0; i--) {
        if (dpArr[i][tempM] !== dpArr[i - 1][tempM]) {
            selectArr.push(i)
            tempM -= weightArr[i]
            selectWeight += weightArr[i]
        }
    }
    console.log('selectWeight: ', selectWeight);
    console.log('selectArr: ', selectArr.reverse());
    console.log('dpArr[arr.length - 1][max]: ', dpArr[arr.length - 1][max]);
    return dpArr[arr.length - 1][max]
}

a = bugQuestion()
console.log('a: ', a);
编辑于 2019-07-31 16:23:21 回复(0)