• 凉风有兴,秋月无边, 亏我思娇的情绪好比度日如年。
  • 虽然我不是玉树临风,潇洒倜傥, 可是我有我广阔的胸襟,加强健的臂腕!

超大背包问题

网站推广 villain 4个月前 (11-19) 23次浏览 已收录 0个评论

有一类背包问题中背包的体积很大但是价值很小,这种背包中如果按照正常的思维来写的话很容易超内存,可以换种思维,dp[I]表示价值为I的价值用的最小空间;
Knapsack problem
Crawling in
process… Crawling
failed

Given a set of n items, each with a weight w[i] and a value
v[i], determine a way to choose the items into a knapsack so that
the total weight is less than or equal to a given limit B and the
total value is as large as possible. Find the maximum total value.
(Note that each item can be only chosen once).


Following n lines provide the information of each item.

The i-th line contains the weight w[i] and the value v[i] of the
i-th item respectively.

1 = number of test cases = 100

1 = n = 500

1 = B, w[i] = 1000000000

1 = v[1]+v[2]+…+v[n] = 5000

All the inputs are integers.


解体思路:首先这个很清楚看出来是个01背包。但是这个背包容量特别大,同时物品的体积很大,总的价值却很少。寻常意义上dp[i]表示背包容量为i时的最大价值,
那么我们把这个dp[]数组的含义改变一下,dp[i]表示装价值为i时所需的最小容量。
感悟:唉,压线过得真持基;
#include
#include
#include
using namespace std;
const int maxn = 550;
const int INF = 0x3f3f3f3f;
int w[maxn], v[maxn];
int dp[5500];
int main(){

freopen(“in.txt”,”r”,stdin);
int T, n,
B;

scanf(“%d”,

while(T–){

scanf(“%d%d”, n,

int V = 0;

for(int i = 1; i i++){

scanf(“%d%d”, w[i], v[i]);

V += v[i];

}

memset(dp,INF,sizeof(dp));

dp[0] = 0;

for(int i = 1; i i++){

for(int j = V; j = v[i]; j–){

dp[j] = min(dp[j],dp[j-v[i]]+w[i]);

// printf(“%d “,dp[j]);

}

}

int ans = 0;

for(int i = V; i i–){

if(dp[i] = B){

ans = i; break;

}

}

printf(“%d\n”,ans);
}
return
0;
}


Villain博客 , 版权所有丨如有问题请联系客服QQ:1004619丨
转载请注明超大背包问题
喜欢 (0)
[gqakcom@126.com]
分享 (0)

您必须 登录 才能发表评论!