首页 > 代码库 > 【限定条件的0-1背包】

【限定条件的0-1背包】

2024-07-26 08:43:14   217人阅读

Perfect decision

TimeLimit: 2 Second MemoryLimit: 32 Megabyte

Totalsubmit: 128 Accepted: 23

Description

有N个物品（1<=N<=100），每个物品都有自己的重量Wi（1<=Wi<=10000）和价值Vi（1<=Vi<=10000）。从N个物品中选择一些，使其价值之和大于M（1<=M<S，S为所有物品价值之和），求满足条件时，重量之和的最小值。

Input

多CASE。对于每组测试：第1行，两个正整数：N，M。第2行到第N+1行，每行两个正整数Vi和Wi。

Output

一个正整数，表示重量之和的最小值。

Sample Input

5 16
3 3
1 1
3 4
5 5
6 6

Sample Output

18

 

 

#include<stdio.h>#include<iostream>#include<string.h>#include<time.h>using namespace std;int n,m;int w[100];int v[100];int f[1000002];int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        memset(f,0,sizeof(f));        int sum=0;        int val=0;        for(int i=0;i<n;i++)        {             scanf("%d%d",&w[i],&v[i]);             sum+=w[i];             val+=v[i];        }        sum-=m;        for(int i=0;i<n;i++)            for(int j=sum;j>=w[i];j--)                f[j]=max(f[j],f[j-w[i]]+v[i]);        int ans=val-f[sum-1];        printf("%d\n",ans);    }}

 

 
 
 
 

【限定条件的0-1背包】


联系
我们