1268：【例9.12】完全背包問題
- 2022 年 5 月 12 日
- 筆記
1268：【例9.12】完全背包問題
時間限制: 1000 ms 記憶體限制: 65536 KB
提交數: 23526 通過數: 12540
【題目描述】
設有nn種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為MM，今從nn種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小於等於MM，而價值的和為最大。
【輸入】
第一行：兩個整數，MM(背包容量，M≤200M≤200)和NN(物品數量，N≤30N≤30)；
第2..N+12..N+1行：每行二個整數Wi,CiWi,Ci，表示每個物品的重量和價值。
【輸出】
僅一行，一個數，表示最大總價值。
【輸入樣例】
10 4 2 1 3 3 4 5 7 9
【輸出樣例】
max=12
程式碼：
 |
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int v[55],w[55],f[205];
int main()
{
int N,V;
cin>>V>>N;
for(int i=1;i<=N;i++)cin>>v[i]>>w[i];
for(int i=1;i<=N;i++)
for(int j=v[i];j<=V;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<"max="<<f[V]<<endl;
}
|
