問題描述
有?N?件物品和一個體積為?M?的背包。第?i?個物品的體積為?vi?，價值為?wi?。每件物品可以使用無限次。
請問可以通過什么樣的方式選擇物品，使得物品總體積不超過?M?的情況下總價值最大，輸出這個最大價值即可。
輸入格式
第一行輸入兩個正整數?N,M。(1≤N,M≤1000)
接下來?N?行，每行輸入兩個整數?vi,wi。(0≤vi,wi≤1000)
輸出格式
輸出一個整數，表示符合題目要求的最大價值。
樣例輸入
4 5
1 2
2 4
3 4
4 5
樣例輸出
10
說明
你可以選擇?1?個第一個物品和?2?個第二個物品。
?
?
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e3+10;
int n, m;
int v[N], w[N];
int dp[N]; //dp[j]表示背包容量為j時的最大價值int main()
{cin>>n>>m;for(int i=1; i<=n; ++i) cin>>v[i]>>w[i];for(int i=1; i<=n; ++i) //遍歷每個物品{//內層循環從v[i]到m正向遍歷，這使得同一物品可以被多次選取for(int j=v[i]; j<=m; ++j){//dp[j]：不選當前物品//dp[j - v[i]] + w[i]：選當前物品dp[j] = max(dp[j], dp[j-v[i]] + w[i]);}}cout<<dp[m];return 0;
}?
