481
რედაქტირება
ზურგჩანთის ამოცანა: განსხვავება გადახედვებს შორის
ნავიგაციაზე გადასვლა
ძიებაზე გადასვლა
→ამოხსნა
|
<source lang="cpp">
#include <iostream>
using namespace::std;
long long weight[100], value[100], dp[100005];
int main() {
// ნივთების რაოდენობა - n
// წონის ლიმიტი - w
cin >> n >> w;▼
for (int j = w; j >= weight[i]; j--){
// თითოეული წონისთვის უნდა გამოვთვალოთ მაქსიმალური ჯამური
// ღირებულება. როგორც ვახსენეთ, ნივთი ან უნდა ავიღოთ, ან არა.
// რადგან უდიდესი ღირებულება გვჭირდება, უნდა გავაკეთოთ ყველაზე
// მომგებიანი არჩევანი.
}
}
▲ for (int i = 0; i < n; i++) {
▲ for (int j = w; j >= weight[i]; j--){
▲ dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
▲ }
▲ cout << dp[w];
▲ return 0;
}
</source>
| |||