【題目描述】
設有n?種物品，每種物品有一個重量及一個價值。但每種物品的數(shù)量是無限的，同時有一個背包，最大載重量為M?，今從n?種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于M?，而價值的和為最大。
【輸入】
第一行:兩個整數(shù)，M?(背包容量，M≤200?≤200)和N?(物品數(shù)量，N≤30?≤30);第22..N＋1?＋1行:每行二個整數(shù)Wi??,Ci??，表示每個物品的重量和價值。文章來源：http://www.zghlxwxcb.cn/news/detail-802658.html
【輸出】
僅一行，一個數(shù)，表示最大總價值。文章來源地址http://www.zghlxwxcb.cn/news/detail-802658.html
【輸入樣例】
10 4
2 1
3 3
4 5
7 9
【輸出樣例】
max=12
#include<bits/stdc++.h>
using namespace std;
int W,n;
int w[35],v[35];
int dp[205];
int main()
{
cin>>W>>n;
int i,j,k;
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++)
{
for(j=W;j>=w[i];j--)
{
for(k=1;k<=j/w[i];k++)
{
dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
}
}
}
cout<<"max="<<dp[W];
return 0;
}到了這里，關于背包~~~~~~~~~3478：【例86.3】 完全背包問題的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
